Ms. Magda likes cookies very much. In the summer she decided to organise an expedition which purpose is to taste wares from each bakery. Our heroine has been thinking about finding as minimal as possible lenght of the track which passes through each bakery exactly once and returns do the start point. She managed to get the table of distances beetween every two bakeries. You, as a good friend of Magda, decided to help her with the problem and here is our purpose: you have to write a program, which calculates a minimal lenght of the track in exchange for cookies. The shorter your track is, the more cookies you get and Magda is more satisfacted.
Example. We've got 4 bakeries: 1, 2, 3, 4. The table of distances looks as follows:
The shortest length equals to 18. An example way how the track may look: 1 -> 4 -> 3 -> 2 -> 1
In the first line the number of bakeries n. Next follow n lines, each consisted of n (n ≤ 400) numbers (which are the distances beetween bakeries). Distance d between any two bakeries a and b is always between 0 and 100 000 (0 ≤ d(a, b) = d(b, a) ≤ 100 000).
In the first line the calculated lenght of your track. In the second line n + 1 numbers separated by whitespaces (from 1 to n including) where the first and the last have to be the same, it's the order of visiting bakeries.
4 0 4 7 3 4 0 5 8 7 5 0 6 3 8 6 0
18 1 4 3 2 1
It's the number of cookies that Magda gives to you, she gives more if the track is shorter.
Exact formula per test case is [x/(length - y)], where length is your answer, while x and y are Magdas constants per test case. Your score will be considered wrong if length > x + y. Constants per test case are created such to allow wide variety of solutions.
- 1 second
Problem source: SPOJ