[BOJ 11657] 타임머신(Python)

문제

타임머신

문제 해설

벨만-포드 알고리즘

벨만 포드 알고리즘의 가장 기본적인 문제이므로 알고리즘을 알고 있다면 풀 수 있습니다.

풀이 코드

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
edges = []
inf = 1e9
dist = [inf] * (n + 1)
dist[1] = 0  # 1번 노드에서 출발

for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((a, b, c))
# 음의 가중치가 존재하기 때문에 다익스트라 사용 불가.
def bellman_ford():
    # 모든 간선을 n-1번 순회하면 음의 순환이 없다는 가정하에
    # 모든 노드까지의 최단 거리를 구할 수 있다.
    # 그러니 총 n번을 순회하고 마지막 n번에 값이 바뀐다면
    # 가중치가 음수인 간선들이 무한 루프를 도는 것이다.
    for i in range(n):
        for a, b, c in edges:
            # 무한이 아니고, 현재 노드를 거쳐 가는 것이 더 비용이 적으면 갱신
            if dist[a] != inf and dist[b] > dist[a] + c:
                if i == n - 1:  # n번째에 갱신된 경우
                    return False
                dist[b] = dist[a] + c
    return True


if not bellman_ford():
    print(-1)
else:
    for x in dist[2:]:
        print(x) if x != inf else print(-1)