백준 온라인 저지, 최단경로 / 5972번: 택배배송 (파이썬 / 백준 골드문제)

문제 주소: https://www.acmicpc.net/problem/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에 있습니다.

다음 지도를 참고하세요.

           [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가 주어집니다.

출력

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

제한

예제 입력 1

6 8
4 5 3
2 4 0
4 1 4
2 1 1
5 6 1
3 6 2
3 2 6
3 4 4

예제 출력 1

5

힌트

W3sicHJvYmxlbV9pZCI6IjU5NzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwZGRcdWJjMzAgXHViYzMwXHVjMWExIiwiZGVzY3JpcHRpb24iOiI8cD5cdWIxOGRcdWJkODAgXHVkNjA0XHVjMTFjXHViMjk0IFx1YjE4ZFx1YmQ4MCBcdWNjMmNcdWQ2NGRcdWM3NzRcdWM1ZDBcdWFjOGMgXHVkMGRkXHViYzMwXHViOTdjIFx1YmMzMFx1YjJlY1x1ZDU3NFx1YzkxOFx1YzU3YyBcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWM5YzBcdWFlMDgsJm5ic3A7XHVhYzA4IFx1YzkwMFx1YmU0NFx1Yjk3YyBcdWQ1NThcdWFjZTAgXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiBcdWQzYzlcdWQ2NTRcdWI4NmRcdWFjOGMgXHVhYzAwXHViODI0XHViYTc0IFx1YWMwMFx1YjI5NCBcdWFlMzhcdWM1ZDAgXHViOWNjXHViMDk4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWMxOGNcdWI0ZTRcdWM1ZDBcdWFjOGMgXHViOWRiXHVjNzg4XHViMjk0IFx1YzVlY1x1YmIzY1x1Yzc0NCBcdWM5MThcdWM1N2MmbmJzcDtcdWQ1NjlcdWIyYzhcdWIyZTQuIFx1YmIzY1x1Yjg2MCBcdWQ2MDRcdWMxMWNcdWIyOTQgXHVhZDZjXHViNDUwXHVjMWUwXHViNzdjXHVjMTFjIFx1Y2Q1Y1x1YzE4Y1x1ZDU1Y1x1Yzc1OCZuYnNwO1x1YzE4Y1x1YjRlNFx1Yzc0NCBcdWI5Y2NcdWIwOThcdWJhNzRcdWMxMWMgXHVjOWMwXHViMDk4XHVhYzAwXHVhY2UwIFx1YzJmNlx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViMThkXHViZDgwIFx1ZDYwNFx1YzExY1x1YzVkMFx1YWM4Y1x1YjI5NCBcdWM5YzBcdWIzYzRcdWFjMDAgXHVjNzg4XHVjMmI1XHViMmM4XHViMmU0LiZuYnNwO04mbmJzcDsoMSAmbHQ7PSBOICZsdDs9IDUwLDAwMCkgXHVhYzFjXHVjNzU4IFx1ZDVkYlx1YWMwNFx1YWNmYywgXHVjMThjXHViNGU0XHVjNzU4IFx1YWUzOFx1Yzc3OCBNICgxICZsdDs9IE0mbmJzcDsmbHQ7PSA1MCwwMDApIFx1YWMxY1x1Yzc1OCBcdWM1OTFcdWJjMjlcdWQ1YTUgXHVhZTM4XHVjNzc0IFx1YWRmOFx1YjgyNFx1YzgzOCBcdWM3ODhcdWFjZTAsJm5ic3A7XHVhYzAxXHVhYzAxXHVjNzU4IFx1YWUzOFx1Yzc0MCBDX2kgKDAgJmx0Oz0gQ19pJm5ic3A7Jmx0Oz0gMSwwMDApIFx1YjljOFx1YjlhY1x1Yzc1OCBcdWMxOGNcdWFjMDAmbmJzcDtcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuIFx1YzE4Y1x1YjRlNFx1Yzc1OCBcdWFlMzhcdWM3NDAgXHViNDUwIFx1YWMxY1x1Yzc1OCBcdWI1YThcdWM1YjRcdWM5YzQgXHVkNWRiXHVhYzA0XHVjNzc4Jm5ic3A7QV9pIFx1YzY0MCZuYnNwO0JfaSAoMSAmbHQ7PSBBX2kgJmx0Oz0gTjsgMSAmbHQ7PSBCX2kgJmx0Oz0gTjsgQV9pICE9IEJfaSlcdWI5N2MgXHVjNzg3XHVjMmI1XHViMmM4XHViMmU0LiBcdWI0NTAmbmJzcDtcdWFjMWNcdWM3NTggXHVkNWRiXHVhYzA0XHVjNzQwIFx1ZDU1OFx1YjA5OCBcdWM3NzRcdWMwYzFcdWM3NTggXHVhZTM4XHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YzViNCBcdWM3ODhcdWM3NDQgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YzJiNVx1YjJjOFx1YjJlNC4gXHViMThkXHViZDgwIFx1ZDYwNFx1YzExY1x1YjI5NCBcdWQ1ZGJcdWFjMDQgMVx1YzVkMCBcdWM3ODhcdWFjZTAgXHViMThkXHViZDgwIFx1Y2MyY1x1ZDY0ZFx1Yzc3NFx1YjI5NCBcdWQ1ZGJcdWFjMDQgTlx1YzVkMCBcdWM3ODhcdWMyYjVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjJlNFx1Yzc0YyBcdWM5YzBcdWIzYzRcdWI5N2MgXHVjYzM4XHVhY2UwXHVkNTU4XHVjMTM4XHVjNjk0LjxcL3A+XHJcblxyXG48cHJlPlxyXG4gICAgICAgICAgIFsyXS0tLVxyXG4gICAgICAgICAgXC8gfCAgICBcXFxyXG4gICAgICAgICBcLzEgfCAgICAgXFwgNlxyXG4gICAgICAgIFwvICAgfCAgICAgIFxcXHJcbiAgICAgWzFdICAgMHwgICAgLS1bM11cclxuICAgICAgICBcXCAgIHwgICBcLyAgICAgXFwyXHJcbiAgICAgICAgNFxcICB8ICBcLzQgICAgICBbNl1cclxuICAgICAgICAgIFxcIHwgXC8gICAgICAgXC8xXHJcbiAgICAgICAgICAgWzRdLS0tLS1bNV0gXHJcbiAgICAgICAgICAgICAgICAzICA8XC9wcmU+XHJcblxyXG48cD5cdWIxOGRcdWJkODAgXHVkNjA0XHVjMTFjXHVhYzAwIFx1YzEyMFx1ZDBkZFx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0Jm5ic3A7XHVjZDVjXHVjMTIwXHVjNzU4IFx1ZDFiNVx1Yjg1Y1x1YjI5NCZuYnNwOzEgLSZndDsgMiAtJmd0OyA0IC0mZ3Q7IDUgLSZndDsgNiBcdWM3ODVcdWIyYzhcdWIyZTQuIFx1YzY1Y1x1YjBkMFx1ZDU1OFx1YmE3NCBcdWM1ZWNcdWJiM2NcdWM3NTggXHVjZDFkXHVkNTY5XHVjNzc0IDEgKyAwICsgMyArIDEgPSA1IFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM3ODVcdWIyYzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjE4ZFx1YmQ4MCBcdWQ2MDRcdWMxMWNcdWM3NTggXHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YWNlMCwmbmJzcDtcdWM5YzBcdWIwOThcdWFjMDBcdWIyOTQgXHVhZTM4XHVjNWQwIFx1YzE4Y1x1Yjk3YyBcdWI5Y2NcdWIwOThcdWJhNzQgXHVjOTE4XHVjNTdjXHVkNTYwIFx1YzVlY1x1YmIzY1x1Yzc1OCBcdWJlNDRcdWM2YTlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YyBcdWNkNWNcdWMxOGMgXHVjNWVjXHViYjNjXHVjNzQwIFx1YzViY1x1YjljOFx1Yzc3Y1x1YWU0Y1x1YzY5ND8mbmJzcDtcdWIxOGRcdWJkODAgXHVkNjA0XHVjMTFjXHViMjk0Jm5ic3A7XHVhYzAwXHViMjk0IFx1YWUzOFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVhY2UwXHViODI0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YzJiNVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1YWNmYyBNXHVjNzc0IFx1YWNmNVx1YmMzMVx1Yzc0NCBcdWMwYWNcdWM3NzRcdWM1ZDAgXHViNDUwXHVhY2UwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBNKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVhZTRjXHVjOWMwIFx1YzEzOCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4Jm5ic3A7QV9pLCBCX2ksJm5ic3A7Q19pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzlkMVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjE4ZFx1YmQ4MCBcdWQ2MDRcdWMxMWNcdWFjMDAgXHVhYzAwXHVjODM4XHVhYzAwXHVjNTdjIFx1YjQyMCBcdWNkNWNcdWMxOGMgXHVjNWVjXHViYjNjXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU2OVx1YjJjOFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI1OTcyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGFja2FnZSBEZWxpdmVyeSIsImRlc2NyaXB0aW9uIjoiPHA+RmFybWVyIEpvaG4gbXVzdCBkZWxpdmVyIGEgcGFja2FnZSB0byBGYXJtZXIgRGFuLCBhbmQgaXMgcHJlcGFyaW5nIHRvIG1ha2UgaGlzIGpvdXJuZXkuIFRvIGtlZXAgdGhlIHBlYWNlLCBoZSBnaXZlcyBhIHRhc3R5IHRyZWF0IHRvIGV2ZXJ5IGNvdyB0aGF0IGhlIG1lZXRzIGFsb25nIGhpcyB3YXkgYW5kLCBvZiBjb3Vyc2UsIEZKIGlzIHNvIGZydWdhbCB0aGF0IGhlIHdvdWxkIGxpa2UgdG8gZW5jb3VudGVyIGFzIGZldyBjb3dzIGFzIHBvc3NpYmxlLjxcL3A+XHJcblxyXG48cD5GSiBoYXMgcGxvdHRlZCBhIG1hcCBvZiBOICgxICZsdDs9IE4gJmx0Oz0gNTAsMDAwKSBiYXJucywgY29ubmVjdGVkIGJ5IE0gKDEgJmx0Oz0gTSAmbHQ7PSA1MCwwMDApIGJpLWRpcmVjdGlvbmFsIGNvdyBwYXRocywgZWFjaCB3aXRoIENfaSAoMCAmbHQ7PSBDX2kgJmx0Oz0gMSwwMDApIGNvd3MgYW1ibGluZyBhbG9uZyBpdC4gQSBjb3cgcGF0aCBjb25uZWN0cyB0d28gZGlzdGluY3QgYmFybnMsIEFfaSBhbmQgQl9pICgxICZsdDs9IEFfaSAmbHQ7PSBOOyAxICZsdDs9IEJfaSAmbHQ7PSBOOyBBX2kgIT0gQl9pKS4gVHdvIGJhcm5zIG1heSBiZSBkaXJlY3RseSBjb25uZWN0ZWQgYnkgbW9yZSB0aGFuIG9uZSBwYXRoLiBIZSBpcyBjdXJyZW50bHkgbG9jYXRlZCBhdCBiYXJuIDEsIGFuZCBGYXJtZXIgRGFuIGlzIGxvY2F0ZWQgYXQgYmFybiBOLjxcL3A+XHJcblxyXG48cD5Db25zaWRlciB0aGUgZm9sbG93aW5nIG1hcDo8XC9wPlxyXG5cclxuPHByZT5cclxuICAgICAgICAgICBbMl0tLS1cclxuICAgICAgICAgIFwvIHwgICAgXFxcclxuICAgICAgICAgXC8xIHwgICAgIFxcIDZcclxuICAgICAgICBcLyAgIHwgICAgICBcXFxyXG4gICAgIFsxXSAgIDB8ICAgIC0tWzNdXHJcbiAgICAgICAgXFwgICB8ICAgXC8gICAgIFxcMlxyXG4gICAgICAgIDRcXCAgfCAgXC80ICAgICAgWzZdXHJcbiAgICAgICAgICBcXCB8IFwvICAgICAgIFwvMVxyXG4gICAgICAgICAgIFs0XS0tLS0tWzVdIFxyXG4gICAgICAgICAgICAgICAgMyAgPFwvcHJlPlxyXG5cclxuPHA+VGhlIGJlc3QgcGF0aCBmb3IgRmFybWVyIEpvaG4gdG8gdGFrZSBpcyB0byBnbyBmcm9tIDEgLSZndDsgMiAtJmd0OyA0IC0mZ3Q7IDUgLSZndDsgNiwgYmVjYXVzZSBpdCB3aWxsIGNvc3QgaGltIDEgKyAwICsgMyArIDEgPSA1IHRyZWF0cy48XC9wPlxyXG5cclxuPHA+R2l2ZW4gRkomIzM5O3MgbWFwLCB3aGF0IGlzIHRoZSBtaW5pbWFsIG51bWJlciBvZiB0cmVhdHMgdGhhdCBoZSBzaG91bGQgYnJpbmcgd2l0aCBoaW0sIGdpdmVuIHRoYXQgaGUgd2lsbCBmZWVkIGVhY2ggZGlzdGluY3QgY293IGhlIG1lZXRzIGV4YWN0bHkgb25lIHRyZWF0PyBIZSBkb2VzIG5vdCBjYXJlIGFib3V0IHRoZSBsZW5ndGggb2YgaGlzIGpvdXJuZXkuPFwvcD5cclxuIiwiaW5wdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogTiBhbmQgTTxcL2xpPlxyXG5cdDxsaT5MaW5lcyAyLi5NKzE6IFRocmVlIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VyczogQV9pLCBCX2ksIGFuZCBDX2k8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogVGhlIG1pbmltdW0gbnVtYmVyIG9mIHRyZWF0cyB0aGF0IEZKIG11c3QgYnJpbmc8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

접근 방법

- 다익스트라 최단경로 알고리즘을 활용해 문제를 해결한다.

코드

# https://www.acmicpc.net/problem/5972
# 접근 방법
# 다익스트라 최단경로 알고리즘을 활용해 문제를 해결한다.

def dijkstra(start):
    distance[start] = 0 
    q = []
    heapq.heappush(q, [0, start])
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for x in graph[now]:
            cost = dist + x[1]
            if distance[x[0]] > cost:
                heapq.heappush(q, [cost, x[0]])
                distance[x[0]] = cost

import sys, heapq
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])
INF = int(1e9)
distance = [INF for _ in range(n+1)]
dijkstra(1)
print(distance[n])