单向TSP Unidirectional TSP

题意翻译

给一个m行n列(m≤10,n≤100)的整数矩阵,从第一列任何一个位置出发每次往右、右上、右下走一格,最终到达最后一列。要求经过的整数之和最小。整个矩阵是环形的,即第一行的上一行是最后一行,最后一行的下一行是第一行。输出路径上每列的行号。多解时输出字典序最小的。 输入有若干组数据: 每组的第1行:m和n,分别为行数和列数。 每组的第2~m+1行:每行n个数,用空格分开,代表整数矩阵。 输出: 每组有两行,第一行是每列的行号,第二行是路径的经过的整数之和。 感谢@lyonlu 提供的翻译

题目描述

[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=52 [PDF](https://uva.onlinejudge.org/external/1/p116.pdf) ![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA116/8f55250e58c560c3ec06a86150f26e2b1e1f75c6.png)

输入输出格式

输入格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA116/801aba8894b1c630f564c73247a3de8b316ca7cf.png)

输出格式


![](https://cdn.luogu.com.cn/upload/vjudge_pic/UVA116/f42899d4753927986e0c7f639bd537f5a3da0a4c.png)

输入输出样例

输入样例 #1

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4
5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3
2 2
9 10 9 10

输出样例 #1

1 2 3 4 4 5
16
1 2 1 5 4 5
11
1 1
19