[백준 11657번] 타임머신 (Python3)

import sys
input = sys.stdin.readline
INF = 10**9

def BF():
  DP = [INF]*N
  DP[0] = 0
  for i in range(N):
    for x,y,w in graph:
      if DP[x] == INF:
        continue
      if DP[y] > DP[x]+w:
        DP[y] = DP[x]+w
        if i == N-1:
          return False
  return DP

N,M = map(int,input().split())

graph = []
for i in range(M):
  x,y,w = map(int,input().split())
  graph.append((x-1,y-1,w))

result = BF()
if result:
  for i in range(1,N):
    if result[i] == INF:
      print(-1)
    else:
      print(result[i])
else:
  print(-1)

 

전형적인 벨만포드 알고리즘 문제이다.

복습하는 겸 풀어보았다.