[백준/Python] 5972번 : 택배 배송

문제

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

---

풀이

택배 배송 문제, 여물을 헛간인 1에서 헛간 N으로 배달하는 것은 여러가지 그래프를 활용하여 풀 수 있다.
그중 가는 길의 길이는 고려하지 않으므로, 다익스트라를 활용하여 풀 수 있다.
입력에 대한 그래프를 구성하는 과정에서, 해당 문제는 간선에 대해 방향을 따지지 않는 무향 그래프 이므로, 입력 시에 양쪽 출력 노드에 대해 값을 추가해주어야 한다.

---

코드

import heapq

INF = int(1e9)
N,M = map(int, input().split())

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

for _ in range(M):
  a,b,c = map(int, input().split())
  graph[a].append((b,c))
  graph[b].append((a,c))

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

  while q:
    dist, now = heapq.heappop(q)
    if distance[now] < dist:
      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]))

dijkstra(1)
print(distance[N])