Non-Stop Travel

David hates to wait at stop signs, yield signs and traffic signals while driving. To minimize this aggravation, he has prepared maps of the various regions in which he frequently drives, and measured the average delay (in seconds) at each of the various intersections in these regions. He wants to find the routes between specified points in these regions which minimize his delay at intersections (regardless of the total distance he has to drive to avoid delays), and has enlisted your assistance in this effort.

Input

For each region, David provides you with a map. The map data first identifies some number of intersections, NI. The regions never include more than 10 intersections. The intersections in each region are numbered sequentially, starting with the number one (1). For each intersection, in turn, the input then specifies the number of streets leading away from the intersection, and for each such street, the number of the intersection to which the street leads, and the average delay, in seconds, that David encounters at that intersection. Following the data for the last intersection in a region there appear the numbers associated with the intersections where David wants to start and end his drive. The entire input consists of a sequence of maps, followed by the single integer zero (0).

Output

For each region, in order, print a single line of output which contains the region number (they, too, are sequentially numbered, starting with 1), a list of the intersection numbers David will encounter in the route with minimum average delay, and the average number of seconds he will be delayed while travelling this route. A suitable format is shown in the example below.

Notes

1. There will always be a unique route with the minimum average delay in each region.
2. A street from intersection I to intersection J is one-way. To represent a two-way street from I to J, the map must also include a route from intersection J to intersection I.
3. There will never be more than one route directly from intersection I to intersection J.

Example

Suppose David wants to travel from intersection 2 to intersection 4 in the region shown in the following map:

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

The input and output for this example is shown as the first case in the Sample Input and Sample Output shown on the next page.

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

---

為了輸出方便, 我把邊跟起點終點全反了

#include <stdio.h>
#include <string.h>
#include <queue>
#define min(x, y) ((x) < (y) ? (x) : (y))
using namespace std;

int map[20][20], test = 0;
void spfa(int st, int ed, int n) {

    int dis[20], used[20], pre[20], tn, i;
    memset(dis, 63, sizeof(dis));
    memset(used, 0, sizeof(used));
    queue<int> Q;
    Q.push(ed);
    dis[ed] = 0;
    while(!Q.empty()) {
        tn = Q.front();
        Q.pop();
        used[tn] = 0;
        for(i = 1; i <= n; i++) {
            if(dis[i] > dis[tn]+map[tn][i]) {
                dis[i] = dis[tn]+map[tn][i];
                pre[i] = tn;
                if(used[i] == 0) {
                    used[i] = 1;
                    Q.push(i);
                }
            }
        }
    }
    printf("Case %d: Path =", ++test);
    i = st;
    do {
        printf(" %d", i);
        i = pre[i];
    } while(i != ed);
    printf(" %d; %d second delay\n", ed, dis[st]);
}
int main() {
    int st, ed, n;
    while(scanf("%d", &n) == 1 && n) {
        memset(map, 63, sizeof(map));
        int i, m, y, v;
        for(i = 1; i <= n; i++) {
            scanf("%d", &m);
            while(m--) {
                scanf("%d %d", &y, &v);
                map[y][i] = min(map[y][i], v);
            }
        }
        scanf("%d %d", &st, &ed);
        spfa(st, ed, n);
    }
    return 0;
}