BNU4206：单向行走
给定一个m*n的矩阵，请写一个程序计算一条从左到右走过矩阵且权和最小的路径。一条路径可以从第1列的任意位置出发，到达第n列的任意位置。每一步只能从第i列走到第i+1列的同一行或者相邻行（第一行和最后一行看作是相邻的）。 12345678910111213141516171819202122232425 例如1 -> 2 -> 23 -> 24 ->25就是一条路径。路径的权和为所有经过的n个方格中整数的和。Input #include <stdio.h>#include <string.h>#include <algorithm>using namespace std;int a[10005][10005];int path[10005][10005];const int inf = 99999999;int main(){ int n,m,i,j,ans,to,v,k,p; while(~scanf("%d%d",&n,&m)) { for(i = 0; i<n; i++) for(j = 0; j<m; j++) scanf("%d",&a[i][j]); for(i = m-2; i>=0; i--)//从第m-2列开始，枚举所有状况 { for(j = 0; j<n; j++) { int minn = inf,id = inf; for(to = -1; to<=1; to++) { v = a[(j+to+n)%n][i+1]; p = (j+to+n)%n; if(minn>v || (minn == v && p<id))//找出最小路径，相同则找字典序小的 { minn = v; id = p; } } a[j][i]+=minn; path[j][i] = id; } } ans = inf; for(i = 0; i<n; i++) { if(ans>a[i][0]) { ans = a[i][0]; k = i; } } printf("%d\n%d",ans,k+1); for(i = 0; i<m-1; i++) { printf(" %d",path[k][i]+1); k = path[k][i]; } printf("\n"); } return 0;}
