실행 시간 제한 | 메모리 제한 |
---|---|
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가 공백으로 구분되어 주어집니다.
- 동주가 가져가야 하는 간식의 최소 개수를 출력합니다.
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
5