[백준] 11657 타임머신

---

한 도시에서 출발하여 나머지 도시까지의 최단 거리를 구하는 문제이다. 간선의 가중치에 음수가 존재할 수 있기 때문에 다익스트라 알고리즘을 사용할 수 없다.

 

음수 가중치를 가지는 간선이 있는 경우 최단 경로를 구하는 알고리즘은 플로이드-와샬, 벨만-포드 알고리즘이 존재한다. 하지만 문제에서 1번 도시에서 출발한다고 명시하였기 때문에 벨만-포드 알고리즘을 사용하는 것이 효율적일 것이다.

 

하지만 벨만-포드 알고리즘을 사용하면 시간초과가 발생한다. 따라서 벨만-포드 알고리즘을 최적화한 SPFA(Shortest Path Faster Algorithm)을 사용해야한다.

 

벨만-포드 알고리즘은 사이클이 발생하지 않게 하기 위해서 정점의 개수 - 1 만큼의 반복을 통해서 최단 경로를 구한다. 하지만 이 경우 반드시 정점의 개수 - 1번 반복하기 때문에 비효율적이라고 볼 수 있다.

 

SPFA는 정점의 거리가 갱신된 경우에만 큐에 정점을 삽입하여 반복하기 때문에 벨만-포드 알고리즘 보다 효율적이다.

 

벨만-포드 알고리즘의 시간 복잡도는 O(정점의 개수 * 간선의 개수) 이며,

SPFA 알고리즘의 시간 복잡도는 O(간선의 개수) 이며 최악의 경우 벨만-포드와 동일하다.

 

from sys import stdin
from collections import deque

readline = stdin.readline

INF = 10000 * 500 + 1


def SPFA():
    dist = [INF] * n
    cycle = [0] * n
    on = [False] * n
    q = deque()
    
    q.append(0)
    dist[0] = 0
    on[0] = True
    while q:
        u = q.popleft()
        on[u] = False

        for v, _w in graph[u]:
            if dist[v] > dist[u] + _w:
                dist[v] = dist[u] + _w
                if not on[v]:
                    q.append(v)
                    on[v] = True
                    cycle[v] += 1

                    if cycle[v] == n:
                        print(-1)
                        return
    all_negative = True
    for i in range(1, n):
        if dist[i] >= 0:
            all_negative = False
    if all_negative:
        print(-1)
        return
    for i in range(1, n):
        print(dist[i] if dist[i] != INF else -1)

if __name__ == "__main__":
    n, m = map(int, readline().split())
    graph = [[] for _ in range(n)]
    for _ in range(m):
        u, v, w = map(int, readline().split())
        graph[u-1].append([v-1, w])

    SPFA()