PLHOP  Plane Hopping
This man has grown so rich that, when he travels between any two locations he always takes at least K flights. In a region of N cities, we need to find the minimal cost required for the man to travel between every pair of cities. There are provisions (especially for this type of rich men,) to fly from ith city to the ith city itself!
Input
T – The number of test cases.
In each test case :
K N
NxN matrix representing the costs of the tickets. The ith line, jth
column’s entry represents the cost of a ticket from city i to city j.
The numbers are of course space separated.
Constraints :
T<=20
N<=50
K<=10^{9}
The cost of each ticket <= 100
Each element of the output matrix will fit into a
64bit integer.
Output
For the ith test case , 1st line is of the form “Region #i:”.
In the following N lines, output an NxN matrix where the jth element
of the ith line represents the minimal cost to travel from city i to
city j with taking at least K flights. The numbers on a line must be
separated by at least one space. Output a blank line after each testcase
(including the last one).
Example
Sample Input:
2
3 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
10999 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
Sample Output:
Region #1:
3 4 5 6
7 8 9 10
11 12 13 14
15 16 17 18
Region #2:
10999 11000 11001 11002
11003 11004 11005 11006
11007 11008 11009 11010
11011 11012 11013 11014
hide comments
Pranav Vaish:
20141224 22:39:28
It's not necessary to mention:


kostya:
20120630 20:44:10
AC for wrong solution... 
Added by:  Prasanna 
Date:  20060113 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:  ByteCode '06 