0212. Nasty Mutant

Input file name:	b.in
Output file name:	b.out
Time limit:	2 s
Memory limit:	64 megabytes

Two guys who fought at ACM contests for almost all their student years have evolved a new kind of business: the shortest path evaluation. So they have founded a new company ACM (Abandon Cruel Meters) to help people to walk less and do more every day of their life. At first everything was fine and the algorithm they wrote at the contests blindly brought them enormous profits. But one day they faced a very strange client. That client was a mutant so he could cross any road in quite different manners. For example, he could merely walk or run or crawl or fly or swim (swim through asphalt???), etc┘ But he also did not like when people laughed at him, so first he selected the path that will allow him to cross it only walking in the shortest time. If there exist several such paths he selected the one which would allow him to run it faster (what if he would prefer running after all!). If there is still a tie, he will select the ⌠best crawling■ path, then best flying, then best swimming and so on┘ If there is still a tie after considering all possible motion types, any of the remaining paths will do. So, you are to help ACM guys to prove that their company is capable of helping even such unordinary clients. Oh, and he is also brain-damaged, so he does not currently remember where his home, his office, his girl lives (btw, she is also a mutant), etc┘ So he asked to find such a path for every pair of source/destination junctions on the city map. Some city roads are one-way, some are two-way. For ease we will consider all of them as one-way. Two-way roads will be given as two one-way roads in the opposite directions.

Input file format

The first line contains three integer numbers: N - the number of road junctions, M √ the number of different roads, and K √ the number of mutant motions types. 0 ≤ N, K ≤ 40. There is no limit for M, except that it will allow reading all the roads and solve the problem with asymptotically suitable algorithm without exceeding the time limit. M lines follow. Each of these lines has the form V1 V2 X1 X2 … XK. V1 is the source junction, V2 is the destination junction of the road described by this line, 1 ≤ V1, V2 ≤ N. Xi is the cost of the road (i.e. travel time) using i▓th mutant motion type. 0 ≤ Xi ≤ 1▓000▓000, 1 ≤ i ≤ K.

Output file format

Your output should contain N2 lines, one for every source-destination pair in the source-major order, each line should contain integers V1 V2 Y1 Y2 … YK giving the cost of the best path (in terms of the selection procedure described above) using only motion of type i on all of its roads from V1 to V2. If there is no path from V1 to V2, output ⌠V1 V2 forget it■ instead (without quotes). Please note again that the order of output lines is fixed, it is source-major order like if you would scan a matrix left to right, row-by-row.

Example:

b.in	b.out
3 3 2 1 2 1 2 2 3 1 2 1 3 2 3	1 1 0 0 1 2 1 2 1 3 2 3 2 1 forget it 2 2 0 0 2 3 1 2 3 1 forget it 3 2 forget it 3 3 0 0

Source: Petrozavodsk Winter 2004. Denis Koshman Contest, Saturday, January 31
Author: Denis Koshman

Discuss       Submit a solution



Printable version