題意：題目翻譯成中文就是無(wú)向旅行商，其實(shí)就是給你一個(gè)n*m的矩陣，要求一條從第一列到最后一列的最小花費(fèi)的路徑，上下可以互通。
解法：看到這題就覺(jué)得和The triangle類似，很快寫(xiě)出代碼，輸出路徑?jīng)]有問(wèn)題，但是題目說(shuō)如果有多條路徑要求字典序最小的那個(gè)。我開(kāi)始是從左往右推，網(wǎng)上看了解題報(bào)告說(shuō)這樣做不能保證字典序最小，要從右往左推，于是改了代碼就A了，至于為什么這樣做就能保證字典序最小還沒(méi)有想明白。
#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;
}