ROHAAN  Defend The Rohan
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
ameyanator:
20180330 13:16:10
Perfect Application of Floyd Warshall Algorithm :)! 

biQar:
20130714 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!

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