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 i-th city to the i-th city itself!
Input
T – The number of test cases.
In each test case :
K N
NxN matrix representing the costs of the tickets. The i-th line, j-th
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<=109
The cost of each ticket <= 100
Each element of the output matrix will fit into a
64-bit integer.
Output
For the i-th test case , 1st line is of the form “Region #i:”.
In the following N lines, output an NxN matrix where the j-th element
of the i-th 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:
2014-12-24 22:39:28
It's not necessary to mention:
|
|
kostya:
2012-06-30 20:44:10
AC for wrong solution... |
Added by: | Prasanna |
Date: | 2006-01-13 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS PERL6 VB.NET |
Resource: | ByteCode '06 |