[백준] 5972번 택배 배송(python)

https://www.acmicpc.net/problem/5972

5972번: 택배 배송

 

1. 난이도 골드5 (🥇) 

 

2. 문제해결 방법

전형적인 다익스트라 문제이다.

 

다익스트라 알고리즘을 사용하고 distance의 마지막 위치를 return 해주면 된다.

 

3. 내가 작성한 코드

import heapq
INF = int(1e9)

n,m = map(int,input().split()) #n헛간 m소

graph = [[] for _ in range(n+1)]
distance = [INF] * (n+1)

for i in range(m):
  a,b,c = map(int,input().split()) #a출발헛간 b도착헛간 c여물
  graph[a].append((b,c))
  graph[b].append((a,c))

def dij():

  q = []
  heapq.heappush(q,(0,1)) #출발지점
  distance[1] = 0

  while q:

    dist, now = heapq.heappop(q)

    if dist > distance[now]:
      continue
    
    for i in graph[now]:
      cost = dist + i[1]

      if cost < distance[i[0]]:
        distance[i[0]] = cost
        heapq.heappush(q,(cost, i[0]))

  return distance[n]

print(dij())

 

4. 메모

 

 graph 에서 1를 꺼내올 때 i[0] = 도착위치 i[1] = 가중치이고,

 

heapq에 삽입할 때는 가중치, 출발위치 순서이다.