99클럽 코테 스터디 31일차 (BOJ 5972 택배 배송)

오늘의 문제: BOJ 5972(택배 배송)

문제 설명

농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 구두쇠라서 최소한의 소들을 만나면서 지나가고 싶습니다.

농부 현서에게는 지도가 있습니다. N (1 <= N <= 50,000) 개의 헛간과, 소들의 길인 M (1 <= M <= 50,000) 개의 양방향 길이 그려져 있고, 각각의 길은 C_i (0 <= C_i <= 1,000) 마리의 소가 있습니다. 소들의 길은 두 개의 떨어진 헛간인 A_i 와 B_i (1 <= A_i <= N; 1 <= B_i <= N; A_i != B_i)를 잇습니다. 두 개의 헛간은 하나 이상의 길로 연결되어 있을 수도 있습니다. 농부 현서는 헛간 1에 있고 농부 찬홍이는 헛간 N에 있습니다.

농부 현서의 지도가 주어지고, 지나가는 길에 소를 만나면 줘야할 여물의 비용이 주어질 때 최소 여물은 얼마일까요? 농부 현서는 가는 길의 길이는 고려하지 않습니다.

문제 해결

가장 기본적인 다익스트라 유형의 문제 입니다. 현서는 1에서만 출발하고 찬홍이는 N에서 출발하기 때문에 다익스트라 알고리즘을 사용해서 1에서 N까지 최소값을 저장하는 dp 배열을 만들고 최소값을 갱신해줍니다. 마지막으로 dp[n]을 출력해주면 되는 문제입니다.

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

n, m = map(int, input().split())

graph = [[] for _ in range(n+1)]
INF = float('inf')
dp = [INF 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))

heap = []
dp[1] = 0
heappush(heap, (0, 1))

while heap:
    cost, node = heappop(heap)

    if dp[node] < cost:
        continue

    for n_node, n_cost in graph[node]:
        t_cost = cost + n_cost
        if dp[n_node] > t_cost:
            dp[n_node] = t_cost
            heappush(heap, (t_cost, n_node))

print(dp[n])