此题是多段图最短路的经典例题
只要逆推就可以了
其实感觉和数字三角形有点像,就是数字三角形的扩展
直接上代码
#include <iostream>
#include <algorithm>
using namespace std;
int a[11][101],d[11][101],next[11][101];
const int INF = 0xfffff; //最大值设置
int first; //记录最小字典序的值
int main(){
int n,m;
while (!cin.eof()){ //输入判断循环
cin>>m>>n;
int ans=INF; //初始化答案
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
cin>>a[i][j]; //输入
for (int j=n;j>0;j--){ //根据DP思想,我们要逆推
for (int i=1;i<=m;i++){
if (j==n) d[i][j]=a[i][j]; //边界条件判定
else {
int row[3]={i,i-1,i+1}; //方向数组
if (i==1) row[1]=m; //边界判定
if (i=m) row[2]=1; //边界判定
sort(row,row+3); //因为在边界地区的字典序不同所以需要排序重新生成最小字典序
d[i][j]=INF; //DP初始化
for (int k=1;k<3;k++){
int v=d[row[k]][j+1]+a[i][j];
if (v<d[i][j]) d[i][j]=v,next[i][j]=row[k]; //DP核心
}
}
if (j==1&&d[i][j]<ans) ans=d[i][j],first=i;
}
}
cout<<first<<endl;
for (int i=next[first][1],j=1;j<=n;i=next[i][j],j++)
cout<<i<<" ";
cout<<endl;
}
return 0; //完美结束
}