[백준 5972] 택배 배송 Python

택배 배송

티어 : Gold 5
시간 제한 : 1 초
메모리 제한 : 128 MB
알고리즘 분류 : 그래프 이론, 다익스트라

 

문제

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

농부 현서에게는 지도가 있습니다. 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 이기 때문입니다.

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

 

입력

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

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

 

출력

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

 

예제 입출력

---

Algorithm

최단거리 - Dijkstra
1. 양방향 그래프 생성
2. Dijkstra 최단거리 구하기

 

Code

def dijkstra(start):
    queue = []
    # 시작 노드로 가는 최단 경로 0으로 설정
    heapq.heappush(queue, (start, 0))
    distance[start] = 0
    
    while queue:
        # 최단거리가 가장 짧은 노드 꺼내기
        now, dist = heapq.heappop(queue)
        
        # 이미 처리된 적 있는 노드인지 확인
        if distance[now] < dist:
            continue

        # 인접한 헛간으로 이동
        for i, C in graph[now]:
            cost = dist + C
            # 현재 노드를 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우
            if cost < distance[i]:
                distance[i] = cost
                heapq.heappush(queue, (i, cost))
    
import heapq
import sys
input = sys.stdin.readline
INF = 10e9

N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
distance = [INF for _ in range(N+1)]
visited = [False 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))

dijkstra(1)
print(distance[-1])

메모리: 51188KB
시간: 968ms