테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 최소비용 구하기 ======

===== 풀이 =====
  * 그냥 표준적인 [[ps:단일_출발지_최단_경로#다익스트라 알고리즘]] 활용 문제. 다익스트라 알고리즘으로 최단 경로를 구하면 된다.
  * 시간복잡도는 O(ElogV).

===== 코드 =====
<dkpr py>
"""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()
</dkpr>
  * Dependency: [[:ps:teflib:graph#dijkstra|teflib.graph.dijkstra]]

{{tag>BOJ ps:problems:boj:골드_5}}