• 양수 가중치를 갖는 방향그래프에서의 최단경로. 따라서, 다익스트라 알고리즘을 쓰면 끝나는 문제이다.
• 문제에서 친절하게 강조했지만, 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의하자. 가장 짧은 간선만 남기면 된다.
• 다익스트라 알고리즘만 돌리면 되니까 시간복잡도는 O(ElogV)

"""Solution code for "BOJ 1753. 최단경로".

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

Tags: [Dijkstra]
"""

import sys
from teflib import graph as tgraph

INF = float('inf')


def main():
    V, E = [int(x) for x in sys.stdin.readline().split()]
    wgraph = [{} for _ in range(V)]
    K = int(sys.stdin.readline())
    for _ in range(E):
        u, v, w = [int(x) for x in sys.stdin.readline().split()]
        if w < (e := wgraph[u - 1]).get(v - 1, INF):
            e[v - 1] = w

    dists = tgraph.dijkstra(wgraph, K - 1)
    print(*('INF' if dist == INF else dist for dist in dists), sep='\n')


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.dijkstra