0170. Travelling Salesman Returns!

Input file name:	salesman.in
Output file name:	salesman.out
Time limit:	3 s
Memory limit:	64 megabytes

Travelling Salesman plans to return to the Alpha Centauri system! All the people wait it! They want new best goods from other systems!

But the Salesman as usual wants to minimize the travel expenses. He selects any starting planet, flies there on the intergalactic spaceship, visits all planets in the system in order which minimizes the total cost, and then flies on the intergalactic spaceship away. Of course he does not want to visit any planet more than once. Your task is to calculate the optimal route for the Salesman. The people can wait no longer!

Input file

The Alpha Centauri system contains n planets. This number is written on the first line of the input file (1 ≤ n ≤ 19). The next n lines contain n numbers each: j-th number of the i-th line is the travel cost from i-th planet to j-th. The numbers are separated by spaces. Numbers a_ii should be ignored. All numbers are positive integers which do not exceed 10⁸.

Output file

Output the minimal total cost in the first line. In the second line output n numbers – the route on which the total cost is minimized.

Examples:

salesman.in	salesman.out
3 8 1 6 3 5 7 4 9 2	5 3 1 2

Source: Petrozavodsk Summer 2003. KOTEHOK's Contest, Sunday, August 31
Author: Andrew Lopatin

Discuss       Submit a solution



Printable version