[백준/파이썬] 1916 최소비용

#문제링크

https://www.acmicpc.net/problem/1916

1916번: 최소비용 구하기

#나의풀이

import sys
import heapq

def dijkstra(start):
    dp[start] = 0
    heap = []
    heapq.heappush(heap, [0, start])

    while heap:
        w, cur  = heapq.heappop(heap)

        if dp[cur] < w:
            continue

        for dest, weight in graph[cur]:
            cost = dp[cur] + weight
            if dp[dest] > cost:
                dp[dest] = cost
                heapq.heappush(heap, [cost, dest])


if __name__=="__main__":
    Node = int(sys.stdin.readline())
    graph = [[] for _ in range(Node+1)]
    dp = [2147000000] * (Node+1)
    M = int(sys.stdin.readline())

    for _ in range(M):
        i, j, value = map(int, sys.stdin.readline().split())
        graph[i].append([j, value])

    start, end = map(int, sys.stdin.readline().split())

    dijkstra(start)
    print(dp[end])

#해설

간단하게 설명하자면 start에서 시작해서 end까지 가는데 최소비용으로 가라는 문제로

읽으면 여러가지로 풀 수 있겠지만 다익스트라가 떠올랐고 다익스트라를 사용해서 풀었습니다.