백준 5972 택배 배송 python

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 -> 2 -> 4 -> 5 -> 6 입니다. 왜냐하면 여물의 총합이 1 + 0 + 3 + 1 = 5 이기 때문입니다.

 

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

입력

첫째 줄에 N과 M이 공백을 사이에 두고 주어집니다.

둘째 줄부터 M+1번째 줄까지 세 개의 정수 A_i, B_i, C_i가 주어집니다.

출력

첫째 줄에 농부 현서가 가져가야 될 최소 여물을 출력합니다.

풀이

import heapq
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
# 헛간의 개수와 노선의 개수를 받아줍니다.

INF = 1e8
# 노선의 개수는 50000이고 각 길에 있는 최대 소의 수는 1000이므로 둘의 곱보다 큰 수를
# 방문하지 않은 헛간까지의 거리로 만들어줍니다.

graph = [[] for _ in range(n + 1)]
visited = [INF for _ in range(n + 1)]
# 모든 헛간에 방문처리를 할 리스트와 헛간에서 출발하는 그래프를 표시할 리스트를 만들어줍니다.

for i in range(m):
    s, e, need = map(int, input().split())
    graph[s].append((need, e))
    graph[e].append((need, s))
    # m번만큼 양방향 노선과 소가 얼마나 있는지 받아주고
    # 양 헛간에서 맞은편 헛간으로 이동하는 방법을 graph에 넣어 추가해줍니다.

def dijkstra(a):
    heap = []
    heapq.heappush(heap, (0, a))
    visited[a] = 0
    # 힙을 만들어 시작점에 가는데 필요한 비용과 시작점을 튜플로 묶은 값을 넣어주고
    # 시작점을 0의 비용이 든다고 방문처리를 해줍니다.

    while heap:
        cost, p = heapq.heappop(heap)
        # 힙에서 꺼낸값을 각각 그 자리까지 도착하는데 든 비용과 위치로 지정해줍니다.

        if visited[p] >= cost:
            for food, target in graph[p]:
                # graph[p]와 연결된 노선을 순회하며 
                new = cost + food
                if visited[target] > new:
                    # 연결된 접점으로 이동하는데 저장되있는 비용보다 적게든다면
                    visited[target] = new
                    heapq.heappush(heap, (new, target))
                    # 이동하고 비용을 갱신해준 뒤 힙에 넣어줍니다.

dijkstra(1)
print(visited[-1])
# 함수를 실핼하고 목적지의 값을 출력해줍니다.