BOJ 11657 타임머신 (벨만-포드 알고리즘)

다익스트라와 거의 같은 방법으로 최소 비용 경로를 찾는 알고리즘이지만, 대신 비용에 음수가 있을 경우를 가정한 방법론.
$G = (V, E)$로 표현되는 그래프에서 시간복잡도는 $O(V * E)$이다. 모든 정점의 수만큼 반복하고($V$만큼), 각 반복마다 모든 간선을 확인하기 때문.

최소거리는 (V-1)번째 반복에서 구해진다. V번째 반복에서 업데이트가 있을 경우 음수 순환이 존재한다는 뜻.

import sys

input = sys.stdin.readline


def main():
    N, M = map(int, input().split())
    edges = [list(map(int, input().split())) for _ in range(M)]

    # bellman-ford
    INF = 1e10
    distance = [INF] * (N + 1)
    # 시작점
    distance[1] = 0
    # 음수 순환이 존재하는지
    is_negative_circular = False
    # V번 반복, E개의 간선 모두 확인
    for j in range(N):
        for i in range(M):
            from_node, to_node, cost = edges[i]
            if distance[from_node] != INF:
                if (distance[from_node] + cost) < distance[to_node]:
                    distance[to_node] = distance[from_node] + cost
                    # 업데이트가 V번째 반복에서 발생했으면 음수 순환이 존재한다는 뜻
                    if j == (N - 1):
                        is_negative_circular = True

    if is_negative_circular:
        print(-1)
    else:
        for i in range(2, N + 1):
            if distance[i] == INF:
                print(-1)
            else:
                print(distance[i])


if __name__ == '__main__':
    main()