3163 : 정기권
- 제한시간
- 2000 ms
- 메모리제한
- 256 MB
- 해결횟수
- 3 회
- 시도횟수
- 31 회
문제
조이가 사는 도시에는 1부터 N까지 번호가 붙어있는 N개의 역과, 두 개의 역을 양방향으로 연결하는 M개의 철로가 있다.
i(1 ≦ i ≦ M)번째 철도 노선은 A_i번째 역과 B_i번째 역을 양방향으로 연결하며, 승차 운임은 C_i원이다.
조이는 S번째 역에서 살고 있으며, T번째 역에 있는 고등학교에 다니고 있다.
때문에 조이는 S번째 역과 T번째 역을 오가는 정기권을 구입하기로 결심했다.
정기권을 구입할 때는 S번째 역과 T번째 역을 연결하는 경로들 중 최소 비용인 경로를 하나 골라야 한다.
지정한 경로에 포함된 철도 노선은 양방향으로, 추가 비용을 들이지 않고 자유롭게 타고 다닐 수 있다.
조이는 U번째와 V번째 역에 있는 서점도 자주 이용하고 있다.
그래서 U번째 역과 V번째 역을 오갈 때 비용이 가능한 작아지도록 정기권을 구입하기로 했다.
여기서 U번째 역에서 V번째 역으로 이동할 때 드는 최소 비용은 다음과 같다.
먼저 U번째 역과 V번째 역을 연결하는 경로를 하나 선택한다.
이 경로에 포함된 철도 노선 i에서 지불해야하는 요금은,
• 철도 노선 i가 정기권에서 지정한 철도 노선에 포함 된 경우 0원
• 철도 노선 i가 정기권에서 지정한 철도 노선에 포함되지 않은 경우 C_i원
이 된다. 총 비용은 모든 철도 노선에 대한 비용의 합이며, 최소 비용은 모든 경로 중 비용의 최솟값이다.
정기권을 구입할 때 지정하는 경로를 잘 선택하여, U번째 역에서 V번째 역으로 이동하는 데 드는 비용의 최솟값을 구하자.
입력형식
출력형식
입력 예6 6 1 6 1 4 1 2 1 2 3 1 3 5 1 2 4 3 4 5 2 5 6 1 |
출력 예2 |
입력 예6 5 1 2 3 6 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 |
출력 예3000000000 |
입력 예8 8 5 7 6 8 1 2 2 2 3 3 3 4 4 1 4 1 1 5 5 2 6 6 3 7 7 4 8 8 |
출력 예15 |
입력 예5 5 1 5 2 3 1 2 1 2 3 10 2 4 10 3 5 10 4 5 10 |
출력 예0 |
입력 예10 15 6 8 7 9 2 7 12 8 10 17 1 3 1 3 8 14 5 7 15 2 3 7 1 10 14 3 6 12 1 5 10 8 9 1 2 9 7 1 4 1 1 8 1 2 4 7 5 6 16 |
출력 예19 |
Hint!