1. 문제 설명

최소 비용 구하기

2. 문제 분석

다익스트라 알고리즘을 통해 주어진 노드에서 다른 모든 노드에 대한 최소 비용을 구한다. 우선순위 큐를 통해 효율적으로 풀 수 있으며, 이때 그래프 구현은 딕셔너리가 편하다.

3. 나의 풀이

import heapq
import sys

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())

nodes = {}
INF = int(1e9)
distances = [INF for _ in range(n+1)]

for _ in range(m):
    tail, head, cost = map(int, sys.stdin.readline().rstrip().split())
    heads = nodes.get(tail, [])
    heads.append([head, cost])
    nodes[tail] = heads
    # 방향 그래프 구현

start, end = map(int, sys.stdin.readline().rstrip().split())
distances[start] = 0
# 자기 자신만 제외하고 나머지 노드는 현재 갈 수 없는 상태(INF)

queue = []
heapq.heappush(queue, [0, start])

while queue:
    cur_cost, cur_node = heapq.heappop(queue)
    # 해당 노드에 갈 수 있는 비용
    
    if distances[cur_node] < cur_cost: continue
    # 현재 최소 비용보다 비싸다면 간주 X
    if not nodes.get(cur_node): continue
    # 해당 노드에서 이어진 다른 노드가 있어야 한다.
    for next_node, next_cost in nodes[cur_node]:
        if distances[next_node] > cur_cost + next_cost:
            # cur_node에서 이어진 next_node로 가는 비용이 현재 최소 비용보다 싸다면 업데이트 후 힙에 넣는다.
            distances[next_node] = cur_cost + next_cost
            heapq.heappush(queue, [cur_cost+next_cost, next_node])

print(distances[end])