[백준 1916 최소비용 구하기] PYTHON

간단한 다익스트라 알고리즘 문제이다.

 

import sys
import heapq


input = sys.stdin.readline

def dijkstra(start, end):
    heap = []
    heapq.heappush(heap, (0, start)) 
    distance = [sys.maxsize] * (N + 1)  
    distance[start] = 0 

    while heap:
        cost, city = heapq.heappop(heap)
        for e, c in bus[city]:
            if distance[e] > cost + c:
                distance[e] = cost + c
                heapq.heappush(heap, (cost + c, e))
    return distance[end]


if __name__ == "__main__":
    N = int(input()) 
    M = int(input())
    bus = [[] for _ in range(N + 1)]
    for _ in range(M):
        a, b, c = map(int, input().split())
        bus[a].append((b, c))
    start, end = map(int, input().split())

    print(dijkstra(start, end))