[백준 11657] 타임머신 (python)

11657번: 타임머신

---

 

벨만-포드 알고리즘을 사용하자!

처음에 시작점이 정해져있고 각각의 나머지 도시로 가는 최단거리를 구하는 것이기에 다익스트라 알고리즘으로 시도했다. 하지만 음의 순환이 있다면 음의 순환을 통해 무한으로 값을 줄일 수 있으므로 다익스트라 알고리즘을 사용하지 못한다고 한다.

다익스트라와 원리는 비슷하지만 queue에 넣고 최소가중치를 찾는 것이 아니라 모든 정점(N개)에 연결되있는 것들을 N-1번 반복한다. N-1번 때도 update가 된다면 음의 가중치가 있다는 뜻이다.

 

1. 시작점에서 각 정점의 걸리는 시간을 저장하는 dist 배열을 생성한다.
2. arr 배열에 간선들의 정보를 저장한다.
3. 정점 1번부터 N까지 연결되어있는 정점의 시간들을 update해준다.
4. 위의 작업을 N-1번 작업해준다.
5. 이 때 N-1번 때도 dist가 update 되었다면 음의 순환이 있다는 뜻으로 무한히 오래전으로 돌릴 수 있으므로 -1을 출력한다.
6. dist 시간이 있다면 출력해주고 없다면 -1을 출력한다.

 

import sys
import heapq
input = sys.stdin.readline

N, M = map(int, input().split())
arr = [[] for _ in range(N+1)]
dist = [sys.maxsize]*(N+1)
dist[1]= 0

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

check = True
for repeat in range(N):
    for i in range(1,N+1):
        for e, w in arr[i]:
            if dist[i]!= sys.maxsize and dist[e] > dist[i]+w:
                dist[e] = dist[i]+w
                if repeat == N-1:
                    check = False

if check:
    for i in dist[2:]:
        if i == sys.maxsize:
            print(-1)
        else:
            print(i)
else:
    print(-1)