[백준] 11657 타임머신 : Bellman-Ford 알고리즘 그자체인 문제 !

처음에 타임머신 & 웜홀 문제 컨셉을 이해하는데 응? 시간이 거꾸로 가 ? 무슨말이지;; 이랬는데 이말인 즉슨, 

가중치가 음수일 수 있다라는 의미이다 

즉, 우리는 최단거리를 구해야 하는데, 다익스트라 방법에서는 음수인 value가 주어지지 않았었다. 

음수인 가중치가 주어지면 ?? 바로바로 우리가 알고리즘 시간에 배웠지만 망각했을 가능성이 큰 Bellman-Ford 방법을 떠올려야 한다 !!

다익스트라와 방법은 유사하나, 다른점은 

노드를 하나씩 돌면서, 최단거리를 갱신해주는 작업을 v-1 번만 수행해야 한다는 점이다

v-1 번 이상일때도 값이 바뀐다는 뜻은 바로 cycle을 돌고 있다는 뜻이다 ..

# 11657 타임 머신

n, m = map(int, input().split())
INF = int(1e9)
dist = [INF] * (n+1)
edges = []
for i in range(m):
    a, b, cost = map(int, input().split())
    edges.append((a, b, cost))

dist[1] = 0

def solve():
    for i in range(n):
        for j in range(m): # edges 확인하기 !!!!
            start, end, cost = edges[j][0], edges[j][1], edges[j][2]

            if dist[start] != INF and dist[end] > dist[start] + cost:
                dist[end] = dist[start] + cost
                if i == n-1:
                    return False
    return True

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