[백준] 파이썬 5972번 : 택배 배송

 

"""
53516KB	276ms
"""
# 최소 여물. 다익스트라

from heapq import *
import sys
input = sys.stdin.readline

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])
    
cost = [1e9 for _ in range(n + 1)]
heap = []
cost[1] = 0
heappush(heap, [0, 1])

while heap:
    cur_cost, cur_node = heappop(heap)
    if cost[cur_node] < cur_cost:
        continue
    for next_node, next_cost in graph[cur_node]:
        if cost[next_node] > cur_cost + next_cost:
            cost[next_node] = cur_cost + next_cost
            heappush(heap, [cur_cost + next_cost, next_node])

print(cost[n])

 

지도가 주어지고, 길을 지날때 소를 만나면 줘야하는 최소 여물은 얼마일까라는 부분에서 다익스트라 문제라는것을 추측할 수 있었다. 

 

그래프를 n+1만큼 생성하고 초기화해주고 반복문을 통해 양방향 간선을 연결하고 비용을 함께 넣어준다. 

최소 비용을 담아줄 cost 배열을 선언하고 모든 노드의 비용을 최대로 초기화한다. 그리고 최솟값을 계속 뽑아내야하기 때문에 heap을 선언해주었다. 출발지점이 되는 1은 0으로 바꾸어주고, 힙에도 총 비용과 노드를 추가해준다. ([0:총비용, 1:노드])

힙이 빌때까지 반복문을 실행하고 힙의 첫번째 요소를 꺼내준다. 만약 힙에서 꺼낸 비용이 cost에 있는 노드의 비용보다 크다면 최소값이 아니니 continue로 넘어가도록 하고, 해당 노드에서 갈수있는 노드들의 최소비용을 알기 위해 반복문을 사용한다. 

현재 비용 + 다음 노드로 갈때 필요한 비용이 cost[다음노드]에 있는 것보다 작다면 최솟값이므로 값을 갱신해준다. 그리고 힙에 넣어서 해당 노드에서 갈 수 있는 노드를 또 탐색하게하고, 힙이 빌때까지 이것을 반복한다. 

그리고 도착지인 n의 최소비용을 출력해주면 된다.

 

 

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

5972번: 택배 배송