[snippet] bellman-ford.py

백준 11657번. 타임머신에 대한 풀이를 Bellman-Ford Algorithm의 스니펫 느낌으로 작성.

• 한 정점에서 다른 모든 정점까지의 Shortest Path(최단 경로) 를 구할 때 사용.
  (가중치가 음수여도 됨.)

import sys
from collections import defaultdict
input = lambda: sys.stdin.readline().rstrip()
INF = int(1e9)

########################

def bellman_ford(start):
    dist[start] = 0
    for _ in range(V-1):
        for i in range(1, V+1):
            if dist[i] == INF:
                continue
            for j, weight in graph[i]:
                dist[j] = min(dist[j], dist[i]+weight)
    
    # check minus cycle
    for i in range(1, V+1):
        for j, weight in graph[i]:
            if dist[i] == INF:
                continue
            if dist[i]+weight < dist[j]:
                raise

########################

V, E = map(int, input().split())
graph = defaultdict(list)
for _ in range(E):
    A, B, cost = map(int, sys.stdin.readline().rstrip().split())
    graph[A].append((B, cost))

dist = [INF] * (V+1) # 1-indexed

try:
    bellman_ford(1)
    for d in dist[2:]:
	    print(d if d != INF else -1)
except:
    print(-1)