파일 업로드

간식 배송

profile
실행 시간 제한메모리 제한
1 초128 MB
📃 해결할 문제

N개의 축사들과 그들을 연결하는 M개의 양방향 길이 있고, 각 길에는 Ci마리의 소가 있으며 소의 길은 다른 두개의 축사Ai와 Bi를 연결합니다. 동주는 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 개의 간식을 주어야 합니다.

💻 입력

- 줄1 : 두 개의 정수 N과 M이 공백으로 구분되어 주어집니다.

- 다음 M개의 줄에는 세 개의 정수 Ai, Bi, Ci가 공백으로 구분되어 주어집니다.

🖨️ 출력

- 동주가 가져가야 하는 간식의 최소 개수를 출력합니다.


💻 예제 입력 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

출처: USACO 2011 March Silver 2