[백준 11657][파이썬] 타임 머신 (벨만 포드)

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

11657번: 타임머신

 

음의 간선을 포함하고 있기 때문에 다익스트라가 아닌 벨만 포드 알고리즘을 사용한다.

 

무조건 음의 간선을 포함한다고 문제가 생기는 것은 아니다.

 

정확히는 음의 간선이 포함된 사이클이 최단 거리를 - ∞로 만들 때 문제가 발생한다.

 

다음과 같은 음의 사이클은 문제가 되지 않는다.

사이클을 반복하면 비용이 증가하기 때문에 최단 거리를 구하는 문제에서는 문제가 되지 않는다.

 

그런데 다음과 같이 비용이 계속 감소하는 음의 사이클에서는 최단 거리를 구할 때 문제가 발생한다.

이 때 벨만 포드 알고리즘을 사용하면 음의 간선이 포함된 그래프에서 최단 거리를 구할 수 있고 음의 사이클 또한 판별할 수 있다.

 

알고리즘의 진행 과정은 다음과 같다.

 

1. 시작할 때 시작 노드의 최단거리는 0으로, 다른 모든 노드까지의 최단 거리를 양의 무한대로 설정한다.
2. 모든 간선을 조사하는데 (노드의 개수 -1 )만큼 반복한다.
3. 특정 노드까지 도달하는데 더 저렴한 경로를 발견하면 그 경로로 최단 거리를 갱신한다.
4. 만약 n-1번 반복을 마치고 한 번 더 반복을 했을 때 최단 경로가 갱신되면 비용이 감소하는 음의 사이클이 있다고 판단한다.

<최종 코드>

import sys
input=sys.stdin.readline
MAX=1e9
n, m = map(int, input().split())
graph=[[] for _ in range(n+1)] #그래프
arr=[MAX]*(n+1)
arr[1]=0
for _ in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c)) #a에서 b로 가는 시간은 c
for i in range(n): 
    for idx, temp in enumerate(graph): #모든 간선 조사
        if idx==0:
            continue
        for to_node, cost in temp:
            if arr[idx]!=MAX and arr[idx]+cost<arr[to_node]: #현재 까지 to_node까지의 비용보다 지금 노드를 거쳐 가는 편이 저렴할 때
                arr[to_node]=arr[idx]+cost #최단 거리 갱신
                if i==n-1: #사이클이 존재
                    print(-1)
                    exit()
for i in range(2, n+1):
    if arr[i]==MAX:
        print(-1)
    else:
        print(arr[i])