题目描述
旅行商简化版欧几里德旅行商(Euclidean Traveling Salesman)问题也就是货郎担问题一直是困扰全世界数学家、计算机学家的著名问题。现有的算法都没有办法在确定型机器上在多项式时间内求出最优解，但是有办法在多项式时间内求出一个较优解。 为了简化问题，而且保证能在多项式时间内求出最优解，J.L.Bentley提出了一种叫做bitonic tour的哈密尔顿环游。它的要求是任意两点(a,b)之间的相互到达的代价dist(a,b)=dist(b,a)且任意两点之间可以相互到达，并且环游的路线只能是从最西端单向到最东端，再单向返回最西端，并且是一个哈密尔顿回路。现在笛卡尔平面上有n(n<=1000)个点，每个点的坐标为(x,y)(-2^31<=x<=2^31,-2^31<=y<=2^31).
输入
第一行一个整数n 接下来n行，每行两个整数x,y，表示某个点的坐标。 输入中保证没有重复的两点，且保证没有两点的x坐标相同，并且保证最西端和最东端都只有一个点。
输出
一行，即最短回路的长度，保留2位小数。
样例输入
7
0 6
1 0
2 3
5 4
6 1
7 5
8 2
样例输出
25.58
dp题，详见代码。
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define MAXN 1000
struct node{
double x,y;
}coor[MAXN+10];
int n;
double f[MAXN+10][MAXN+10],dis[MAXN+10][MAXN+10];
bool cmp(node a,node b){
return a.x<b.x;
}
double dist(int i,int j)
{
long long p=coor[i].x-coor[j].x,q=coor[i].y-coor[j].y;
return sqrt(p*p+q*q);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&coor[i].x,&coor[i].y);
sort(coor+1,coor+n+1,cmp);
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
f[i][j]=1e24;
for(int j=1;j<i;j++)
dis[i][j]=dis[j][i]=dist(i,j);
}
f[2][1]=dis[1][2];
for(int i=3;i<=n;i++){
int j;
for(j=1;j<i-1;j++)
f[i][j]=f[i-1][j]+dis[i-1][i];
j=i-1;
for(int k=1;k<i-1;k++)
f[i][j]=min(f[i][j],f[i-1][k]+dis[k][i]);
}
printf("%.2lf\n",f[n][n-1]+dis[n-1][n]);
return 0;
}