ROHAAN - Defend The Rohan

no tags 

Kingdom of Rohan is under attack! There are N vital army stations. King will decide what army should be guarding what station, to get the best strategic advantage against Sauron attacks. All armies are already in some stations, but not necessarily the stations required by the king. As a result armies will have to be moved. Distances between any pair of stations are known. They are not necessarily symmetrical, because road from station A to B could be different than road from B to A. When a army moves, it doesn't have to take a direct road and instead can choose to cross other stations, if that results in a shorter path.

Given the distances between stations and king's relocation orders, find the minimum total travel distance for all the armies.

Input

First line contains an integer T, number of test cases. Then the description of T test cases follow. Each test case starts with an integer N, which is the total number of army stations. Next N lines have N integers each, description of distances. b'th integer on line a is the distance from station a to station b. Description of kings orders follows. In a first line, a single integer R, number of orders. Next R lines will contain two integers s and d each, describing an order to move an army from station s to d.

Constrains:

1 <= T <= 50

1 <= N, R <= 50

1 <= distance <= 10^6

1 <= s, d <= N

Output

Print a single line for each test case. A string "Case #t: " without quotes, where t is the number of test case, starting from 1. Following the string, you must print the total distance armies must travel during relocation.

0 <= total distance <= 10^7

Example

Input:
1
3
0 1 1
1 0 1
1 9 0
2
2 1
3 2

Output:
Case #1: 3

hide comments
biQar: 2013-07-14 15:48:23

I think the Time Limit is very strict for Java solutions. Please check the Time Limit for Java. I have submitted a code in Java which will take the input by using "BufferedReader" and print a garbage output. I got TLE for that instead of Wrong Answer!
-(prassi)-TL Modified to Comfort JAVA solutions. You can resubmit your solution
-(Reply) Thank you :)

Last edit: 2013-07-15 03:52:33

Added by:Syntax Terror
Date:2013-06-27
Time limit:0.339s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own