11657_타임머신(벨만포드)

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

11657번: 타임머신

 

 

 

처음에 다익스트라 알고리즘을 살짝 변형해서 모든 간선을 뒤지도록 변형해서 풀려고 했는데 실패했다... 그래서 힌트에 있는대로 벨만 포드 알고리즘을 공부해 보았다.

 

아래와 같은 간선이 있다고 생각해보자.

 

 

입력케이스로 따지면 아래와 같다.

 

4 6
1 4 10
1 3 8
3 4 1
1 2 5
2 4 3
2 3 1

 

 

 

 

4개의 점이 있기에 3번 반복을 하면 음수가 껴있는 상태에서도 최단거리를 구할 수 있다. 이는 조금있다가 다시 설명해 보겠다!

 

먼저 우리는 distance를 저장할 INF * (n+1) 배열을 만들어 둘 것이다. 구할 점이 1이므로 distance[1] = 0으로 만들어주고 생각해보자.

 

모든 간선을 한번씩 수행하면서 방문했던 노드이고, 그 가중치가 더 적다면 값을 초기화 해준다.

 

자, 예를 들어 

 

1 4 10
1 3 8
3 4 1

 

다음 과정을 수행한다고 생각해보자.

 

1 -> 4 번까지가 10번이므로 distance[4]를 10으로 만들면 된다.

1 -> 3 번까지가 8번이므로 distance[3]을 8로 만을면 된다.

3 -> 4 번까지가 1번인데 우리는 이미 1->3번 이 8인걸 알고 있다. 8+1인 9가 원래 distance[4]에 들어있던 10보다 작으니 확장해준다.

 

 

위 과정을 n-1번 반복한다면

 

[1000000000, 0, 1000000000, 1000000000, 10]
[1000000000, 0, 1000000000, 8, 10]
[1000000000, 0, 1000000000, 8, 9]
[1000000000, 0, 5, 8, 9]
[1000000000, 0, 5, 8, 8]
[1000000000, 0, 5, 6, 8]
--------
[1000000000, 0, 5, 6, 8]
[1000000000, 0, 5, 6, 8]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
--------
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
--------
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
[1000000000, 0, 5, 6, 7]
--------

 

위와 같은 형태로 저장이 될 것이다.

 

n-1번까지 반복하면 최종 값을 구할 수 있는데, 만약 n번 반복했는데도 값이 갱신된다면??? 무한히 갱신되는 값, 즉 무한히 음수로 반복되는 부분이 있는 것이므로 생각하면 된다.

 

 

import sys
input = sys.stdin.readline
INF = int(1e9)

n,m = map(int,input().split())
edges = []
distance = [INF] * (n+1)

for _ in range(m):
    a,b,c = map(int,input().split())
    edges.append((a,b,c))


def f(start):
    distance[start] = 0

    for i in range(1,n+1):

        for j in range(m):
            s,e,cnt = edges[j]

            if distance[s] != INF and distance[e] > distance[s] + cnt:
                distance[e] = distance[s] + cnt

                if i == n:
                    return True
    return False

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