You've successfully subscribed to ムえのBLOG
Great! Next, complete checkout for full access to ムえのBLOG
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.

题解 UVA116 【Unidirectional TSP】

. 1 min read

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

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

直接上代码

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


本站总访问量 正在加载今日诗词....