백준 1916 최소비용 구하기

과정

• 다익스트라
• 간선 정보를 입력 graph에 반영
• heapq 를 사용해서, 비용이 제일 작은 것부터 확인
• 해당 위치에서 이어진 곳으로 가는 데 비용 확인하고, 기존보다 적으면 갱신

import sys
import heapq

# 다익스트라
INF = 1e9

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

input = sys.stdin.readline

graph = [[] for _ in range(N)]
for _ in range(M):  # 입력 값 반영 (노드, 거리) 꼴
    s, e, d = map(int, input().split())
    graph[s - 1].append((e - 1, d))

def dijkstra(start):
    # init
    dp = [INF] * N
    q = []
    heapq.heappush(q, (0, start))
    dp[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        
        # 이미 처리한 곳
        if dp[now] < dist:
            continue
            
        # 이어진 곳으로 가는 데에 거리 확인
        for i in graph[now]:
            cost = i[1] + dist
            if dp[i[0]] > cost:
                dp[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
                
    return dp

a, b = map(int, input().split())
print(dijkstra(a-1)[b-1])