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

백준 1916번 : 최소비용 구하기

(문제 바로가기)

 

 

내 코드

import sys, heapq
from collections import defaultdict

input = sys.stdin.readline
INF = int(1e9)
n = int(input())  # 도시의 개수
m = int(input())  # 버스의 개수
graph = defaultdict(list)  # 버스 정보
for _ in range(m):
    s, e, c = map(int, input().split())
    graph[s].append((e, c))
start, end = map(int, input().split())  # 출발점과 도착점 도시번호

distance = [INF] * (n + 1)

queue = []
heapq.heappush(queue, (0, start))
while queue:  # dijkstra 수행
    dist, curr = heapq.heappop(queue)

    if distance[curr] < dist:  # 기존 거리보다 멀다면 고려하지 않아도 됨
        continue

    for next in graph[curr]:
        cost = dist + next[1]
        if distance[next[0]] > cost:  # 기존보다 단축할 수 있다면
            distance[next[0]] = cost
            heapq.heappush(queue, (cost, next[0]))

print(distance[end])