194. 타임 머신

백준

1. 벨만-포드 알고리즘

import sys, collections

INF = float('inf')
input = sys.stdin.readline
graph = collections.defaultdict(list)

n, m = map(int, input().split())
for _ in range(m):
  a, b, c = map(int, input().split())
  graph[a].append([b, c])

def bellman_ford(start):
  dist = [INF] * (n + 1)
  dist[start] = 0

  for _ in range(n - 1):
    for u in range(1, n + 1):
      for v, c in graph[u]:
        if dist[v] > dist[u] + c:
          dist[v] = dist[u] + c
  
  for u in range(1, n + 1):
    for v, c in graph[u]:
      if dist[v] > dist[u] + c:
        return False

  return dist

dist = bellman_ford(1)

if dist == False:
  print(-1)
else:
   for i in range(2, n+1):
     print(dist[i] if dist[i] < INF else -1)