백준 11657 타임머신

failed

답

import sys
input = sys.stdin.readline
INF = sys.maxsize

n, m = list(map(int, input().rstrip().split()))
edges = []
dist = [INF] * (n + 1)
dist[1] = 0

for _ in range(m):
    a, b, c = list(map(int, input().rstrip().split()))
    edges.append((a, b, c))

isCycle = False
for i in range(n):
    for start, end, time in edges:
        if dist[start] != INF:
            distance = dist[start] + time
            if distance < dist[end]:
                if i == n - 1:
                    isCycle = True
                dist[end] = distance

if isCycle:
    print(-1)
else:
    for d in dist[2:]:
        if d >= INF: print(-1)
        else: print(d)

아무 생각 없이 다익스트라로 풀다가 뭔가 이상함을 감지!
그러나 음수 사이클을 어떻게 해결할 방법이 생각이 안나서 찾아보니
벨만 포드 알고리즘을 사용해야하는거였다ㅠㅠ
이부분 구현은 잘 몰라서 보면서 풀었다.
한 번 더 풀 예정