백준 11657 - 타임머신 (파이썬)

Answer

from sys import stdin

input = stdin.readline
INF = int(1e9)

def bellman_ford():
    for count in range(N):
        for i in range(1, N + 1):
            for next_node, weight in graph[i]:
                if dp[i] != INF and dp[next_node] > dp[i] + weight:
                    dp[next_node] = dp[i] + weight

                    if count == N - 1:
                        return False
                        
    return True

N, M = map(int, input().split())
graph = [[] for _ in range(N + 1)]
dp = [INF] * (N + 1)
dp[1] = 0

for _ in range(M):
    A, B, C = map(int, input().split())
    graph[A].append((B, C))

if bellman_ford():
    for i in dp[2:]:
        print(i if i != INF else -1)
else:
    print(-1)