题意：找最短路，知道三种行走方式，给出图，求出一条从左边到右边的最短路，且字典序最小。
用dp记忆化搜索的思想来考虑是思路很清晰的，但是困难在如何求出字典序最小的路。
因为左边到右边的字典序最小就必须从左边开始找，于是我们可以换个思路，dp时从右边走到左边，这样寻找路径就可以从左向右了。
代码：
/*
* Author: illuz
* Blog: http://blog.csdn.net/hcbbt
* File: uva116.cpp
* Create Date: 2013-09-20 20:56:07
* Descripton: dp, memorial
*/
#include
#include
using namespace std;
const int MAXN = 102;
int dis[MAXN][MAXN], map[MAXN][MAXN], n, m;
int cg(int x) {
if (x == 0) x = n;
else if (x == n + 1) x = 1;
return x;
}
int dp(int x, int y) {
x = cg(x);
if (dis[x][y] != -0xffffff) return dis[x][y];
return dis[x][y] = map[x][y] + min(min(dp(x - 1, y + 1), dp(x, y + 1)), dp(x + 1, y + 1));
}
void print(int x, int y) {
if (y < m)
printf("%d ", x);
else {
printf("%d\n", x);
return;
}
int a = {cg(x - 1), cg(x), cg(x + 1)};
sort(a, a + 3);
int tt = dis[x][y] - map[x][y];
if (tt == dis[a[0]][y + 1])
print(a[0], y + 1);
else if (tt == dis[a ][y + 1])
print(a , y + 1);
else
print(a , y + 1);
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++) {
scanf("%d", &map[i][j]);
if (j == m) dis[i][j] = map[i][j];
else dis[i][j] = -0xffffff;
}
int Min = 0xffffff, t, rx, ry;
for (int i = 1; i <= n; i++) {
t = dp(i, 1);
if (t < Min)
rx = i, Min = t;
}
print(rx, 1);
printf("%d\n", Min);
}
return 0;
}