题意：一个m*n的矩阵，每个格子有个值，现每列取一个值，使取出的值总和最小，并输出路径。（下一个取值只能取现所在行或上一行或下一行）
题目链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=114&problem=52
——>>简单dp，设d[i][j]为从第i行第j列出发的最短路径和。
状态转移方程：
d[i][j] = min(d[i][j+1], d[i-1 == 0 ? m : i-1][j+1]) + MAP[i][j];
d[i][j] = min(d[i][j], d[i+1 == m+1 ? 1 : i+1][j+1]+MAP[i][j]);
递推边界：
d[i][n] = MAP[i][n];
#include <cstdio>
#include <algorithm>using namespace std;const int INF = 214748364;
int d[20][110], MAP[20][110];int main()
{int m, n, i, j;while(~scanf("%d%d", &m, &n)){for(i = 1; i <= m; i++)for(j = 1; j <= n; j++)scanf("%d", &MAP[i][j]);for(i = 1; i <= m; i++) d[i][n] = MAP[i][n];for(j = n-1; j >= 1; j--) //dp求解for(i = 1; i <= m; i++){d[i][j] = min(d[i][j+1], d[i-1 == 0 ? m : i-1][j+1]) + MAP[i][j];d[i][j] = min(d[i][j], d[i+1 == m+1 ? 1 : i+1][j+1]+MAP[i][j]);}int min_sum = INF, min_id = 1; //找最小值及其行号for(i = 1; i <= m; i++)if(d[i][1] < min_sum){min_sum = d[i][1];min_id = i;}int sum = min_sum - MAP[min_id][1]; //处理输出printf("%d", min_id);for(j = 2; j <= n; j++){if(min_id == 1){bool ok = 0;for(i = 1; i <= 2; i++){if(sum == d[i][j]){printf(" %d", i);sum -= MAP[i][j];min_id = i;ok = 1;break;}}if(!ok){printf(" %d", m);sum -= MAP[m][j];min_id = m;}}else if(min_id == m){bool ok = 0;if(sum == d[1][j]){printf(" 1");sum -= MAP[1][j];min_id = 1;ok = 1;}if(!ok){for(i = m-1; i <= m; i++){if(sum == d[i][j]){printf(" %d", i);sum -= MAP[i][j];min_id = i;break;}}}}else{for(i = min_id-1; i <= min_id+1; i++)if(sum == d[i][j]){printf(" %d", i);sum -= MAP[i][j];min_id = i;break;}}}printf("\n%d\n", min_sum);}return 0;
}