Category
알고리즘  DFS/BFS

[11657] 타임머신

by Hwang

문제

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

풀이

최단 거리를 효율적으로 구할 수 있는 알고리즘으로 다익스트라 알고리즘이 있지만 음의 가중치가 존재한다면 정확한 최단 거리를 구할 수 없습니다. 이 문제에는 음의 가중치를 가진 간선이 존재하므로 벨만 포드 알고리즘을 이용해서 풀 수 있습니다.

N-1번 반복하며 모든 간선을 확인하면서 최단 거리를 구하는 방식입니다. 여기서 N-1번 반복하는 이유는 최단 거리를 찾기 위한 길이가 최대 N-1이기 때문입니다.

음의 가중치가 존재하는 그래프는 음수 사이클이 존재할 수 있습니다. 만약 음수 사이클이 존재한다면 최단 거리는 한 없이 작아지기 때문에 값을 구할 수 없게됩니다. 따라서 N-1 번의 반복 후에도 최단 거리가 갱신되는지 확인해주어야합니다.

import sys

N, M = map(int, sys.stdin.readline().split())
edges = [list(map(int, sys.stdin.readline().strip().split()))for _ in range(M)]
dist = [sys.maxsize] * (N + 1)

def bf(start):
    dist[start] = 0
    for i in range(N):
        for j in range(M):
            s, e, cost = edges[j]
            if dist[s] != sys.maxsize and dist[s] + cost < dist[e]:
                dist[e] = dist[s] + cost
                if i == N - 1:  # 음수 사이클 확인
                    return False
    return True

if bf(1):
    for i in dist[2:]:
        print(i if i != sys.maxsize else -1)
else:
    print(-1)


 Comment