Alex is a Truck Driver who wants to find the quickest way to deliver goods to multiple cities. He knows the distances between his destinations, but you need to write a program to help him find the quickest way to deliver goods to them.
The first line of input gives the number of cities Alex needs to deliver goods to. Every line that follows gives the distance between the cities. The second line of input is always the distance between the first and second cities. If there is a third city, the third line of input is the distance between the first and third city. When to distance to the first city has been given for all cities, the next lines of input gives the distance between the the second city and every other city (except the first, as that information as already been given). This continues until every combination has been given. Sample inputs:
//Number of cities 4 //A -> B 2 //A -> C 4 //A -> D 3 //B -> C 5 //B -> D 1 //C -> D 3 3 6 4 2
The output should print the quickest way to deliver goods to every destination in the form
A -> C -> D -> C -> A (For every output, the reverse of will also work. You only need to print one solution). Alex ALWAYS starts at
A and must always return to
A at the end (as
A is where he lives). Here are the outputs for the sample inputs above:
A -> B -> D -> C -> A A -> C -> B -> A
The shortest code wins.