题意：题目翻译成中文就是无向旅行商，其实就是给你一个n*m的矩阵，要求一条从第一列到最后一列的最小花费的路径，上下可以互通。
解法：看到这题就觉得和The triangle类似，很快写出代码，输出路径没有问题，但是题目说如果有多条路径要求字典序最小的那个。我开始是从左往右推，网上看了解题报告说这样做不能保证字典序最小，要从右往左推，于是改了代码就A了，至于为什么这样做就能保证字典序最小还没有想明白。
#include <stdio.h>
#include <string.h>
#define N 15
#define M 105
#define INF 1 << 29
int dir[3][2] = {{-1, -1}, {0, -1}, {1, -1}};
int a[N][M], b[N][M], p[N][M], s[M];
int main()
{
int n, m, x, y, ans, top;
while(~scanf("%d %d", &n, &m))
{
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
memset(p, -1, sizeof(p));
for(int i = 1; i <= n; i++)
b[i][m] = a[i][m];
for(int i = 1; i <= n; i++)
for(int j = 1; j < m; j++)
b[i][j] = INF;
for(int j = m ; j > 1; j--)
for(int i = 1; i <= n; i++)
{
for(int k = 0; k < 3; k++)
{
x = i + dir[k][0];
y = j + dir[k][1];
if(x < 1) x = n;
if(x > n) x = 1;
if(b[i][j] + a[x][y] < b[x][y])
{
b[x][y] = b[i][j] + a[x][y];
p[x][y] = k;
}
}
}
ans = INF, y = 1, top = 0;
for(int i = 1; i <= n; i++)
{
if(b[i][1] < ans)
{
ans = b[i][1];
x = i;
}
}
s[top++] = x;
while(p[x][y] != -1)
{
int t = p[x][y];
x -= dir[t][0], y++;
if(x > n) x = 1;
if(x < 1) x = n;
s[top++] = x;
}
for(int i = 0; i < top; i++)
{
printf("%d", s[i]);
if(i != top - 1) printf(" ");
else printf("\n");
}
printf("%d\n", ans);
}
return 0;
}