PIEK2 - PIEK

no tags 

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. Don't dissapoint her, she's pretty hot.

 

Example 

We've got 4 bakeries: 1,2,3,4.

The table of distances looks as follows:


1 2 3 4
1 0 4 7 3
2 4 0 5 8
3 7 5 0 6
4 3 8 6 0

The shortest lenght equals to:18.

An example way how the track may look:1->4->3->2->1

Input

In the first line the number of bakeries (n).

Next follow n lines, each consisted of n numbers (which are the distances beetween bakeries).

Output

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.

n<=400

Example

Input:
4
0 4 7 3
4 0 5 8
7 5 0 6
3 8 6 0
Output: 18
1 4 3 2 1

Score:

It's the number of cookies that Magda gives to you, she gives more if the track is shorter.

hide comments
jcode777: 2019-02-10 10:46:42

Isn't this the Travelling Salesman problem?!? I can't spot the difference.

parimala rangan: 2014-12-19 19:18:23

should we always start at bakery 1 or do we start anywhere?

(Tjandra Satria Gunawan)(曾毅昆): 2013-05-26 22:54:06

@Marek Mystkowski: Hi, I make BFK_AUTO problem, and I still learning (beginner) about SPOJ judge, could you help me: Can I know your "judge" and "master judge" source code for this problem? And how can you output user's running time on *spoj_u_info?

EDIT(Tjandra): Thanks for your reply :-)

Last edit: 2013-06-04 21:05:57
Marek Mystkowski: 2012-09-02 17:15:09

always:|AB|==|BA|
can be:
|AB|+|BC|<|AC|
|AB|+|BC|>|AC|

Last edit: 2012-09-02 17:25:28
Mitch Schwartz: 2012-09-02 01:56:45

Is it guaranteed that the distance from bakery A to bakery B is the same as the distance from B to A?
-->answer: yes

Also, maybe it's worth mentioning that based on the example, we cannot assume the triangle inequality holds, since 2->1->4 is shorter than 2->4.

Edit: Thanks for the reply.

Last edit: 2012-09-02 21:26:25

Added by:Marek Mystkowski
Date:2012-08-13
Time limit:0.200s-0.600s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64