백준 1916 : 최소비용 구하기 (Python)

본문 링크

import sys,heapq
input=sys.stdin.readline

def Dijkstra(start,end):
    dp = [INF] * (N + 1) ; dp[start]=0
    heap = [] ; heapq.heappush(heap,(0,start))

    while heap:

        value,node = heapq.heappop(heap)

        if dp[node]<value:
            continue

        for next_value,next_node in graph[node]:
            next_value+=value

            if next_value<dp[next_node]:
                dp[next_node]=next_value

                heapq.heappush(heap,(next_value,next_node))
    return dp[end]


INF=int(1e9)

N=int(input())
M=int(input())

graph=[ [] for _ in range(N+1) ]

for i in range(M):

    a,b,c=map(int,input().split())
    graph[a].append((c,b)) #단방향.

start,end=map(int,input().split())
print(Dijkstra(start,end))

📌 어떻게 접근할 것인가?

다익스트라 기초 문제입니다.
다만 1번노드부터 $N$ 번노드까지의 최단경로가 아니라 문제에서 주어지는 두 노드에 대한 최단경로를 구하는 것이기 때문에 함수의 매개변수를 활용해서 시작점을 입력값으로 정해준뒤에 그곳부터 출발하여서 최단경로를 구하였습니다.

백준 1753 : 최단경로 와 유사한 문제입니다.