• 그래프에서 최단 경로를 찾는 기본적인 문제. 걸리는 시간이 음수일수도 있으므로, 벨만포드 알고리즘이나 SPFA를 사용해야한다. 단일 출발지 최단 경로 (Single Source Shortest Path)에서 언급한대로 SPFA를 사용해서 풀었다.
• SPFA의 시간복잡도는 O(VE).

""""Solution code for "BOJ 11657. 타임머신".

- Problem link: https://www.acmicpc.net/problem/11657
- Solution link: http://www.teferi.net/ps/problems/boj/11657

Tags: [SPFA]
"""

import sys
from teflib import tgraph

INF = float('inf')
START = 0

def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(N)]
    for _ in range(M):
        A, B, C = [int(x) for x in sys.stdin.readline().split()]
        try:
            min_edge_cost = wgraph[A - 1][B - 1]
            wgraph[A - 1][B - 1] = min(min_edge_cost, C)
        except KeyError:
            wgraph[A - 1][B - 1] = C

    dist = tgraph.spfa(wgraph, START)
    if -INF in dist:
        print(-1)
    else:
        for dist_to_i in dist[1:]:
            print('-1' if dist_to_i == INF else dist_to_i)


if __name__ == '__main__':
    main()

• Dependency: teflib.tgraph.spfa