• 그냥 표준적인 다익스트라 알고리즘 활용 문제. 다익스트라 알고리즘으로 최단 경로를 구하면 된다.
• 시간복잡도는 O(ElogV).

"""Solution code for "BOJ 1916. 최소비용 구하기".

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

Tags: [Dijkstra]
"""

import sys
from teflib import graph as tgraph

INF = float('inf')


def main():
    N = int(sys.stdin.readline())
    M = int(sys.stdin.readline())
    wgraph = [{} for _ in range(N)]
    for _ in range(M):
        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

    source, dest = [int(x) for x in sys.stdin.readline().split()]
    answer = tgraph.dijkstra(wgraph, source - 1, dest=dest - 1)[dest - 1]
    print(answer)


if __name__ == '__main__':
    main()

• Dependency: teflib.graph.dijkstra