[백준][다익스트라] 5972. 택배 배송

5972. 택배 배송

5972번: 택배 배송

 

• 다익스트라
  • heap을 사용해서 거리가 짧은 값을 먼저 불러옴
  • distance를 처음에 모두 INF로 초기화
  • graph : defaultdict()
    • key: start_node
    • value: (distance, end_node)
  • 매번 최소 거리로 업데이트
  • 📍heap 생성시 그냥 리스트 만들어서 heapq.heappush 

 

#가중치 있는 최단거리: 다익스트라
import heapq
from collections import defaultdict

n,m=map(int,input().split())
distance=[int(1e9) for _ in range(n+1)]
queue=[]
graph=defaultdict(list)

for _ in range(m):
    x,y,v=map(int,input().split())
    graph[x].append((v,y))
    graph[y].append((v,x))

distance[1]=0
heapq.heappush(queue,(0,1))
def dijkstra():
    while queue:
        dist, start=heapq.heappop(queue)
        if distance[start]<dist: continue

        for next_dist, next_node in graph[start]:
            if distance[next_node]>dist+next_dist:
                distance[next_node]= dist+next_dist
                heapq.heappush(queue,(dist+next_dist, next_node))

dijkstra()

print(distance[n])