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

백준 5972 - 택배 배송

시간 제한 1초, 메모리 제한 128MB

# 조건

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

• 농부 현서에게는 지도가 있습니다.
• 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에 있습니다.

다음 지도를 참고하세요.

       [2]---
      / |    \
     /1 |     \ 6
    /   |      \
 [1]   0|    --[3]
    \   |   /     \2
    4\  |  /4      [6]
      \ | /       /1
       [4]-----[5] 
            3  

농부 현서가 선택할 수 있는 최선의 통로는 1 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

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

# 접근 방법

• 그래프의 관계의 수가 최악의 경우에 크기 때문에, 시간 및 메모리 초과를 조심해야 된다.
• 따라서 일반 bfs가 아닌 heapq를 사용한 다익스트라로 풀어준다.
• 해당 그래프간의 관계를 graph에 기록해주고, visited를 노드의 수만큼 생성 후 q에 [현재까지의 비용, 현재 노드]를 넣어주고 탐색을 시작한다.
• 다음 노드까지 가는 비용 + 현재까지의 비용이 visited에 기록된 값보다 작다면 갱신하고 heappush로 q에 넣어준다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

from heapq import heappop, heappush

def solve():
    N, M = map(int, input().split())
    graph = [[] for _ in range(N+1)]
    q = []
    for _ in range(M):
        a, b, c = map(int, input().split())
        heappush(graph[a], [c, b])
        heappush(graph[b], [c, a])

    visited = [float('inf')] * (N+1)
    heappush(q, [0, 1])
    visited[1] = 0

    while q:
        val, now_node = heappop(q)
        if now_node == N:
            print(val)
            break

        for cost, next_node in graph[now_node]:
            if visited[next_node] > cost+val:
                visited[next_node] = cost+val
                heappush(q, [val+cost, next_node])

if __name__ == "__main__":
    solve()