TSP

Description

邮递员在送信时，为了节省路途，自己规定：每次总是从n个村子中选择第一个村子出发，途中每个村子仅且经过一次，送完所有的信，而且最后要回到原来出发的城市。已知各个村子的道路连通情况。请你帮邮递员选择一条合适的路线，假设每次选择村子（包括出发的村子）时优先选择序号最小的村子。

Input

第一行：整数n：村子的个数，n<=10。 接下来是一个n*n的矩阵，表示n个村子的路径长度情况a[i,j]≥0。

Output

一条可行的路线，和路线的最短距离

Sample Input

4
0 6 7 9
8 0 9 7
5 8 0 8
6 5 5 0

Sample Output

1 2 4 3 1
23

Structure

• /input/zidianxu.in 内包含路径长度相同，多条路径选择字典序的数据
• brutal.cpp 是该程序的暴力代码
• duipai.py 是用来对拍的python程序
• gen.py 是随机数据生成器
• notdic.cpp 是第一版错误的没有按照字典序排序输出路径的dp代码
• TSP.cpp 是该程序正解