[백준] 11657 - 타임머신 [Python(파이썬)]

문제

www.acmicpc.net/problem/11657

11657번: 타임머신

풀이

음수 가중치가 주어졌기 때문에 벨만 포드 알고리즘을 사용했다. 나무위키에 나와있는 슈도 코드를 그대로 구현하면 된다.

'시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다.'라는 조건이 있는데, 말이 너무 어렵다.

쉽게 말해서 음수 사이클을 찾으라는 이야기다.

음수 사이클을 체크하는 부분만 넣어주면 문제없이 해결할 수 있다.

코드

import sys, collections

INF = float('inf')
g = collections.defaultdict(list)

n, m = map(int, sys.stdin.readline().split())
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().split())
    g[a].append([b, c])

def bellman_ford(s):
    dist = [INF] * (n+1)
    dist[s] = 0
    for _ in range(n-1):
        for u in range(1, n+1):
            for v, c in g[u]:
                if dist[v] > dist[u] + c:
                    dist[v] = dist[u] + c
    for u in range(1, n+1):
        for v, c in g[u]:
            if dist[v] > dist[u] + c:
                return False
    return dist

dist = bellman_ford(1)

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