题解 UVA116 【Unidirectional TSP】

此题是多段图最短路的经典例题
只要逆推就可以了

其实感觉和数字三角形有点像，就是数字三角形的扩展

直接上代码

#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;	//完美结束
}