RDNWK  Road Network
In a country of N cities, the government would like to develop a new system that can answer drivers’ queries to find the shortest path between 2 cities in the country road network. However, some cities are more exciting than others, and drivers would prefer driving through them. Last month, a voting for the most exciting cities in the country was conducted, and a ranking of the P most exciting cities has been made. The government decided to utilize this ranking so that drivers can find the shortest path between 2 cities that only goes through the first K cities of the ranking as intermediate cites on the road. Hence, the query is defined as: the source city, the destination city, and K for the first K cities from the ranking. (Note that some cities may not be exciting at all, and so they will not be included in the ranking, i.e. P <= N)
Given undirected graph representing the country cities, and ranked list of exciting cities, you are to answer Q quires, each one asking for the shortest path between 2 cities utilizing only the first K cities from the ranked list.
For example, given the graph in the sample (4 cities and ranked list [2 1])
1 Query(k=0, Src=3, dest=4): means no cities to use as intermediate, hence only direct path allowed à 34 with cost 10 2 Query(k=1, Src=3, dest=4): means we can use first city on list (2), hence we can choose between paths (34, 324) à path 324 with cost 8 is best 3 Query(k=2, Src=3, dest=4): means we can use first 2 cities on list (1, 2), hence we can choose between paths (34, 324, 3214) à path 3214 with cost 6 is best

Input Specification:
The first line of input contains an integer T that represents the number of test cases, then follow T test cases, each in following format:
Line 1
N (1 ≤ N ≤ 150), the number of cities of the country
N1 lines follow, where ith line represents ith city connections' costs, Ci,j is the cost of edge (i, j), if there is no edge between i, j then Ci, j = 1 else, 1 ≤ Ci,j ≤ 10000
C1, 2 C1, 3 ... C1, N
C2, 3 C2, 4 ... C2, N
...
CN1, N
Line N+1
P (0 ≤ P ≤ N), represents the size of ranked list
Line N+2
P spaceseparated list of distinct cities ids (1 <= city id <= N)
Line N+3
Q (1 ≤ Q ≤ 6000), represents the number of queries
Q lines follow
K source destination
....
Note that: 0 ≤ K ≤ P, 1≤ source ≤ N and 1≤ destination ≤ N
Output Specification:
For each test case, output a single line of output in the form “Case K: A1 A2 …Aq” where K is the number of the test case and [A1 A2 … Aq] are the answers for the Q quires. Each answer is the shortest path cost between the 2 given cities using the first only K cities of given list as intermediate cities. In case no path between 2 cities, the answer is 1
Sample input:
1
4
2 1 3
1 7
10
2
2 1
3
0 3 4
1 3 4
2 3 4
Sample Output:
Case 1: 10 8 6
hide comments
glays:
20170714 13:26:52
O(Q * N^3) ?! With Q=6000 and N=150 ?


rohit9934:
20170712 17:48:00
Floyd Warshall Works fine.


hodobox:
20170223 15:31:28
My complexity is slightly worse than O(T*N^3), still had no problems (won't say exactly cause I think it spoils the problem somewhat) 

nada elnokaly:
20130917 10:46:04
5s o.O ! my code with complexity O(T*N^3) gives TLE ! 
Added by:  Mostafa Saad Ibrahim 
Date:  20111113 
Time limit:  2.426s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  10th Egyptian Collegiate Programming Contest 