문제
동현이는 최단거리(경로) 알고리즘를 연구하고 있다. 자동차 네비게이션과 도로 지도 등 여러 곳에 응용분야가 많다고 들었기 때문이다. 최근, 연구 중에 아주 놀라운 점을 하나 발견하였는데 최단거리가 최단시간을 의미하지 않는다는 것이었다.
거리는 조금 멀더라도 시간은 최단 거리보다 덜 걸리는 경우가 종종 있었다.
그래서 동현이는 최단 거리는 아니지만 최단 거리에 가까운 경로에 관심을 가지게 되었다.
동현이는 최단 거리에 가까운 경로를 거의 최단 경로라 명명하고 그 정의를 “최단 경로에 포함되지 않는 경로들만으로 이루어진 가장 짧은 경로”라고 정했다.
예를 들어 도로 지도를 그래프 형태로 나타낸 아래 그림을 보자. 원은 특정장소를 나타내고 화살표는 일방통행 도로를 나타낸다. 아래 그림에서 굵은 실선은 최단경로로서 이 그림에서는 두 가지가 나온다. 점선은 거의 최단경로로서 최단 경로에 포함되지 않는 경로로 이루어진 가장 짧은 경로이다. 짐작하겠지만 거의 최단 경로는 여러 가지가 나올 수도 있고 경로가 없을 수도 있다.
지도 정보가 주어질 때 거의 최단 경로를 구하는 프로그램을 작성하시오.
입력
입력은 5이하의 테스트 케이스로 이루어진다.
각 테스트 케이스의 첫 행에는 장소의 수 N( 2 <= N <= 500)과 도로의 수 M(1 <= M <= 10,000)이 공백을 구분하여 입력된다.
두 번째 행에는 출발지 번호 S와 도착지 번호 D가 공백을 구분하여 입력된다.
(S ≠ D ; 0 ≤ S, D < N) 장소 번호는 0번부터 N-1번까지이다.
세 번째 행부터 M개의 행에 걸쳐 각 도로의 정보 U, V, P가 입력된다. U도시에서 V도시로 가는 거리가 P라는 의미이다.
(U ≠ V ; 0 ≤ U, V < N ; 1 ≤ P ≤ 1,000)
입력의 끝은 0 0 이다.
출력
각 테스트 케이스에 대한 거의 최단경로를 행으로 구분하여 출력한다.
거의 최단경로가 없는 경우 –1을 출력한다.
예제
7 9
0 6
0 1 1
0 2 1
0 3 2
0 4 3
1 5 2
2 6 4
3 6 2
4 6 4
5 6 1
4 6
0 2
0 1 1
1 2 1
1 3 1
3 2 1
2 0 3
3 0 2
6 8
0 1
0 1 1
0 2 2
0 3 3
2 5 3
3 4 2
4 1 1
5 1 1
3 0 1
0 0
5
-1
6
태그
출처
South America Regional Contests 2008 A
로그인해야 코드를 작성할 수 있어요.