341 - Non-Stop Travel

David討厭在開車的時候等紅綠燈，為了避免多餘的等待時間，他規劃了他常行駛的路段，並統計各路段的平均等待時間(以秒為單位)，他希望找到一條路徑使得從起點到終點的總等待時間最短(他不在乎行駛的距離長短)。

Input

對於每組測試資料，David提供了一個地圖，每個地圖的第一個整數NI表示節點的數目，節點數最多不會超過10個，且由1開始作編號。接下來的每一列依序為各個節點到其他節點的路徑，例如第一列為 2  3 3  4 6，表示有兩條路徑，節點1通往節點3的等待時間為3秒，節點1通往節點4的等待時間為6秒。最後一列有兩個整數指示起點與終點。當NI=0表示測試資料結束。

Output

請對每組測試資料輸出資料編號、路徑沿途經過的節點編號、共等待的秒數，其格式請參考範列資料。

Notes

1. 最少等待時間的路徑一定唯有一條。
2. 每個路段皆是單向的。
3. 由 I 到 J 的路段最多只會有一條。
   

Example

第一組範例資料的示意圖如下：

+---------------+                   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

Sample Input

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

Sample Output

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

原文出處