BOJ 5972 택배 배송

문제

접근 방법

정해진 두 점 간의 최단 거리를 구하는 문제이고 weight가 다 양수이므로 dijkstra를 사용했다. distances 배열을 초기화할 때 아예 큰 수로 해야겠다.

정답 코드

import sys
import heapq

input = sys.stdin.readline
'''
두 점의 최단거리를 구하는 문제에 양수 weight이므로 다익스트라 사용
'''

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])

q = []
heapq.heappush(q, (0,1))
distances = [int(1e9)]*(n+1)
distances[1] = 0
while q:
  mid_cost, mid_node = heapq.heappop(q)
  if distances[mid_node] < mid_cost:
    continue
  for end_node, end_cost in graph[mid_node]:
    new_dist = mid_cost + end_cost
    if new_dist < distances[end_node]:
      distances[end_node] = new_dist
      heapq.heappush(q, (new_dist, end_node))

print(distances[n])