[백준] 1916 최소비용 구하기 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/1916
• 🔑  Dijkstra 알고리즘

import sys
from collections import defaultdict
from heapq import heappush, heappop
input = sys.stdin.readline

n = int(input())    # 도시 개수
m = int(input())    # 버스 개수
graph = defaultdict(list)

for i in range(m):
    s, e, c = map(int, input().split())
    graph[s].append((c, e))                # 출발지 : [(비용, 도착지)]

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

INF = int(1e9)
cost = [INF] * (n+1)
cost[start] = 0
q = []
heappush(q, (0, start))

while q:
    now_cost, now = heappop(q)
    if now_cost > cost[now]:    # 같은 경로로 갈 때 비용이 더 들면 넘기기
        continue
    for next_cost, next in graph[now]:
        newCost = now_cost + next_cost
        if cost[next] > newCost:
            cost[next] = newCost
            q.append((newCost, next))

print(cost[end])