Time Limit : 5 Second
Memory Limit : 128 MB
Submission: 694
Solved: 128
Description
This problem gives you a graph which contains vertex set V, arcs E and w(i,j)--the weight between the vertex i and vertex j.
Now, to make the problem a little more interesting, we define a set Vi is a subset of V, and define length(Vi, x) = min{length(y, x) | y is a vertex in Vi), x is a vertex in the graph, and length(y, x) is the length of the shortest path between x and y;
Your task is that: giving you the vertex set V1 and V2, you should calculate the length(V1, x) for every vertex x in V2;
Input
The first line a integer T specifies the number of the test cases, T <= 10.
The second line is two integers v and e(v <= 20000, e <= 100000), specifies the number of the vertex and the number of the arcs.
Then following e lines, every line contains three integers: vi, vj, w(i,j). You can assume that w(i,j) is a positive integer.
The next line contains a single number n(n <= 300) specifies the number of vertex in V1, then the next line contains n integers describe the vertex in V1.
The next line contains a single number m(m <= 30) specifies the number of vertex in V2, then the next line contains m integers describe the vertex in V2.
Output
You should output the results with the following formate:

Case caseNumber:
x1: length(V1, x1)
x2: length(V1, x2)
.
.
.

xi is the i-th element in V2, length(V1, xi) is the length described above, or if there is no path from V1 to xi, you should print:
xi: No path
sample input
1
4 5
2 1 2
2 3 4
1 3 3
4 3 6
4 2 7
2
1 2
2
4 3
sample output
Case 1: 
4: No path 
3: 3
hint
source
Man yl
Submit