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