1080 - The length
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