문제1591--운송 문제

1591: 운송 문제

실행시간 제한: 10 Sec  메모리사용 제한: 128 MB
제출: 407  통과: 107
[제출] [채점기록] [묻고답하기]

문제 설명

 

 

 

위 그림은 여러 개의 도시들과 각 도시들을 잇는 도로를 나타냅니다. 도로들 위에 쓰여 있는 숫자는 도로의 길이를 뜻합니다. 특정한 시작 도시에서부터 끝 도시까지 물품을 운송하고 싶습니다. 이 때 택할 수 있는 가장 짧은 경로의 길이를 계산하는 프로그램을 작성하세요.

 

입력 설명

입력의 첫 줄에는 테스트 케이스의 수 C (<= 50) 이 주어집니다. 각 테스트 케이스의 첫 줄에는 도시의 수 N (<= 10000) 과 도로의 수 M (<= 20000) 이 주어집니다. 각 도시는 0 부터 N-1 까지의 번호로 표현됩니다. 그 후 줄에 각 3개의 정수로 각 도로의 정보가 주어집니다. 도로의 정보는 a b c 로 표현되며, 이 때 이 도로는 a 번과 b 번 도시 사이를 이으며 길이는 c 입니다. 모든 도로는 양방향 통행이 가능합니다.

시작 도시는 항상 0 번, 끝 도시는 항상 N-1 번이라고 가정하며, 이와 같은 경로는 언제나 존재한다고 가정합니다.

 

 

 

출력 설명

각 테스트 케이스마다 가장 짧은 경로의 길이를 출력합니다.

 

입력 예시 Copy

1
7 14
0 1 3
0 2 10
0 3 9
3 4 4
3 5 16
3 1 12
1 2 4
1 2 10
1 4 3
1 5 10
5 4 9
4 6 4
5 6 16
2 6 30

출력 예시 Copy

10

출처/분류