[최단 경로] 백준 11657번: 타임머신 / 골드 4**

https://www.acmicpc.net/problem/11657

11657번: 타임머신

아직은 생소한 벨만-포드 알고리즘이 필요한 문제다.

벨만-포드 알고리즘과 다익스트라의 차이점은 벨만-포드는 음수 가중치가 있는 경우에도 최단 경로를 찾을 수 있다.

공통점은 시작 노드를 특정하고 그 노드에서 다른 노드까지의 거리를 구한다는 것이다.

 

원리 자체는 플로이드-워셜과 비슷하다는 느낌을 받았다.

다만 벨만-포드는 음수 사이클에 빠질 위험이 있기 때문에 이 여부를 한번 확인해주어야 한다.

 

암튼 코드가 좀 길어서 익숙해지기 전까지는 통암기... 가 필요할 거 같다...!

import sys
import collections

n, m = map(int, input().split())

graph = collections.defaultdict(list)
for i in range(m):
    u, v, w = map(int, input().split())  # start, end, weight
    graph[u].append([v, w])

inf = sys.maxsize
dist = {}
pre = {}
for i in range(1, n+1):
    dist[i] = inf
    pre[i] = None

dist[1] = 0

for _ in range(m - 1):
    for node in graph:
        for neighbor, weight in graph[node]:
            if dist[node]==inf:
                continue
            if dist[neighbor] > dist[node] + weight:
                dist[neighbor] = dist[node] + weight
                pre[neighbor] = node

# check negative cycle
for node in graph:
    for neighbor, weight in graph[node]:
        if dist[node] == inf:
            continue
        if dist[neighbor] > dist[node] + weight:
            print(-1)
            quit()

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