백준 11657 <타임머신> Python

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

11657번: 타임머신

---

간선 중 음의 가중치를 지닌 간선이 있기 때문에 최단거리 알고리즘 중 벨만-포드 알고리즘을 사용해야 합니다. 벨만 포드 알고리즘은 모든 노드를 돌아다니며 이어진 간선을 최신화 해주는 알고리즘으로 조금 비효율적인 다익스트라로 보일 수 있지만 모든 노드를 돌아다니며 최적화해주는 특성 탓에 음의 간선이 포함되어 있어도 해를 찾을 수 있다는 장점이 있습니다.

또 음의 루프가 있는지 확인해야 합는데, 방법은 벨만-포드 알고리즘을 한번 돌린 후 한번 더 돌렸을 때 최단거리 리스트가 최신화된다면 이미 탐색을 끝냈음에도 최단 거리를 만들 수 있다는 말이므로 음의 루프가 있다는 말이 됩니다.

---

import sys

from collections import deque

 

def solution(N, M, data_list):

    # 트리

    tree = [[] for _ in range(N+1)]

    for start, end, time in data_list:

        tree[start].append([end, time])

    # 최대 시간

    inf = float('inf')

    # 걸리는 시간 리스트

    time_list = [inf for _ in range(N+1)]

    time_list[1] = 0

    # 벨만-포드

    # 탐색 시작 노드

    for start_node in range(0, N):

        # 현재 탐색 노드

        for now_node in range(start_node, start_node+N):

            # 다음 노드

            # 탐색 시작 노드부터 순환, [1, 2, 3] -> [2, 3, 1] -> [3, 1, 2] 식으로

            for next_node, time in tree[now_node%N + 1]:

                # 다음 노드까지의 시간이 최단시간보다 짧으면 갱신

                if time_list[now_node%N + 1] + time < time_list[next_node]:

                    time_list[next_node] = time_list[now_node%N + 1] + time

    # 음의 루프가 있는지 확인

    for start_node in range(0, N):

        # 현재 탐색 노드

        for now_node in range(start_node, start_node+N):

            # 다음 노드

            # 탐색 시작 노드부터 순환, [1, 2, 3] -> [2, 3, 1] -> [3, 1, 2] 식으로

            for next_node, time in tree[now_node%N + 1]:

                # 다음 노드까지의 시간이 최단시간보다 음의 루프

                if time_list[now_node%N + 1] + time < time_list[next_node]:

                    print(-1)

                    return

    # 음의 루프가 없으면 순서대로 출력

    print(*[time if time != inf else -1 for time in time_list[2:]])

N, M = map(int, sys.stdin.readline().strip().split())

data_list = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(M)]

solution(N, M, data_list)