[백준/python] 5972: 택배배송

5972번: 택배 배송 (acmicpc.net)

노드와 비용을 입력받고 최소 비용이 되는 길로 가야겠다

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

import heapq
n,m=map(int,input().split()) 
graph=[[] for _ in range(n+1)]
for _ in range(m):
    a,b,c=map(int,input().split()) 
    graph[a].append((b,c))
    graph[b].append((a,c))

INF=int(1e9)
dist=[INF]*(n+1) 

def dijkstra(start):
    visit=[]
    q=[]
    heapq.heappush(q,(0, start))
    dist[start]=0

    while q:
        distance, now= heapq.heappop(q)
        if distance> dist[now]: continue
        for i in graph[now]:
            cost= distance + i[1]
            if cost< dist[i[0]]:
                dist[i[0]]=cost
                heapq.heappush(q,(cost, i[0]))
        visit.append(now)

dijkstra(1)
print(dist[n])

평범하게 다익스트라 함수를 짠다. 헛간 1에서 출발한다. 힙큐를 이용해서 가장 작은 비용을 기록하다보면 dist[n]에 최종 최소비용이 남는다.