Amit goes for Vacations
All submissions for this problem are available.
Amit wants to go on vacations with his family. He visits a travel agent. He provides him various offers. But the twist is that the packages offered by the travel agent consist of only few cities . Amit has the choice of selecting the starting city and the ending city. But it costs different for different routes. Amit wants to be economical and therefore wants to spend least amount of money. But still he wants to know all the possible routes and their corresponding fares. Unfortunately, travel agent only has the list of fares between adjacent cities. He is not so good at Mathematics. He needs your help in calculating all the possible routes and their fares.
Cities are numbered from 1 to n.
First line contains no. of test cases t.
First line of each test case contains no. of cities available with travel agent n
Second line of each test case contains no. of pairs of adjacent cities e
Following e lines in each test case contains 3 space separated integers A,B,C
B - city adjacent to A
C- cost of travelling from A to B.
For each test case output n lines where ith line contains n integers.
jth integer representing minimum cost of traveling from ith city to jth city.
If it is not possible to visit a jth city from ith city then output -1 at corresponding location.
Input: 1 4 4 1 2 8 1 3 9 1 4 12 3 4 2 Output: 0 8 9 11 -1 0 -1 -1 -1 -1 -1 0 2 -1 -1 -1 0 Constraints: 1<=t<=500 1<=n<=100 1<=A,B<=n 1<=C<=50
|Time Limit:||0.114286 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.