UVa 341. Non-Stop Travel

341 - Non-Stop Travel

Time limit: 3.000 seconds

안멈추는 여행

David는 운전할 때 정지 신호와 양보신호, 그리고 신호등의 삼색 신호에 따라 기다리는 것을 싫어합니다. 이러한 짜증을 줄이기 위해서 평소에 자주 가는 곳들의 지도를 준비한 뒤 각 지역들의 교차로마다 평균적으로 얼마나 멈추게 되는지를 초단위로 잽니다. David는 이제 당신의 도움을 받아서, 각 지역의 특정한 두 지점을 놓고, 그가 한 지점에서 다른 한 지점으로 갈 때까지 걸리는 지연시간을 최소로 할 수 있는 방법을 찾고 싶어합니다. 이 때, 지연시간을 최소로 하기 위하여 총 운전거리가 늘어나는 것은 상관하지 않습니다.

입력

각 지역에서 David는 당신에게 지도를 줄겁니다. 지도에 나와있는 데이터의 첫번째 숫자는 교차로의 개수를 의미하는 N이고 각 지역마다 교차로는 10개가 넘지 않습니다. 각 지역의 교차로는 순서대로 (1)부터 숫자를 매깁니다. 각 교차로에는 대해 입력할 값은 순서대로 다른 교차로로 가는 길이 총 몇 개나 있는지를 나타내는 숫자와 각 길이 몇 번 교차로로 가는 길인지를 나타내는 숫자와, 각 교차로에서 David가 지연될 초를 나타내는 숫자를 입력합니다. 데이터에 따라 각 지역의 마지막 교차로 다음 줄에는 David가 운전을 시작하길 원하는 지점과 끝내길 원하는 지점에 대한 숫자가 적혀있습니다. 모든 지도의 입력은, 하나의 정수 (0)을 입력하는 것으로 끝냅니다.

출력

각 지역에 대해 한 줄로 출력하는데 1부터 시작하는 지역을 나타내는 숫자와, David가 지연되는것을 최소화한 이동경로를 지나갈 때 만나게 될 교차로들의 각 번호와, 그 경로로 이동할 시 걸리게 될 지연시간을 나타냅니다. 아래 예시에 나올 출력 방법을 참고하세요.

알림

1. 각 지역은 지연시간을 최소화하는 유일한 경로가 존재합니다.
2. 교차로 I 에서 교차로 J로 가는 길은 일방통행입니다. 교차로 I에서 교차로 J로 가는 양방향 길을 나타내려면 지도에는 교차로 J에서 교차로 I로 가는 길을 보여줘야 합니다.
3. 교차로 I에서 교차로 J로 한번에 가는 방법은 단 하나 뿐입니다.

예시

다음 지도에서 David가 2번 교차로에서 4번 교차로로 가기를 원한다고 가정해보면:

                +---------------+                   From To Delay
                |               V                     1   3   3
                1<------2------>3------>4<------5     1   4   6
                |       |               ^       ^     2   1   2
                |       +---------------|-------+     2   3   7
                |                       |             2   5   6
                +-----------------------+             3   4   5
                                                      5   4   7

밑에 나올 예시의 1번 케이스대로 입력 및 출력하면 됩니다.

입력 예시

5
2  3 3   4 6
3  1 2   3 7   5 6
1  4 5
0
1  4 7
2 4

2
1   2 5
1   1 6
1 2

7
4   2 5   3 13   4 8   5 18
2   3 7   6 14
1   6 6
2   3 5   5 9
3   6 2   7 9    4 6
1   7 2
0
1 7

0

출력 예시

Case 1: Path = 2 1 4; 8 second delay
Case 2: Path = 1 2; 5 second delay
Case 3: Path = 1 2 3 6 7; 20 second delay