题目
Description
2000MS/65536K
John Doe, a skilled pilot, enjoys traveling. While on vacation, he rents a small plane and starts visiting beautiful places. To save money, John must determine the shortest closed tour that connects his destinations. Each destination is represented by a point in the plane pi = < xi,yi >. John uses the following strategy: he starts from the leftmost point, then he goes strictly left to right to the rightmost point, and then he goes strictly right back to the starting point. It is known that the points have distinct x-coordinates.
Write a program that, given a set of n points in the plane, computes the shortest closed tour that connects the points according to John’s strategy.
Input
The program input is from a text file. Each data set in the file stands for a particular set of points. For each set of points the data set contains the number of points, and the point coordinates in ascending order of the x coordinate. White spaces can occur freely in input. The input data are correct.
Output
For each set of data, your program should print the result to the standard output from the beginning of a line. The tour length, a floating-point number with two fractional digits, represents the result. An input/output sample is in the table below. Here there are two data sets. The first one contains 3 points specified by their x and y coordinates. The second point, for example, has the x coordinate 2, and the y coordinate 3. The result for each data set is the tour length, (6.47 for the first data set in the given example).
Simple input
3
1 1
2 3
3 1
4
1 1
2 3
3 1
4 2
Simple output
6.47
7.89
题目分析
这个题的算法学名叫做“双调欧几里得旅行商问题”，即在平面上的n个点，确定一条闭合的线连接这n个点且使这条线最短，这类的问题建议只考虑双调旅程来化简，即严格按照从最左端邹至最右端，然后再从最右端走回最左端的出发点。
既然所求的结果是n个点连接成一个闭合的多边形，那么在这n个点中存在着这样的子结构，(i,j)为从i开始由右到左直到1，在由1开始由左到右直到j，这之间会经过1到max(i,j)之间的所有的点并且只有一次。定义这样最短的路线为d(i,j)
即我们最后要求的解则应该是d(n,n)
子结构分为三种情况:1.当j<i-1时,2.当j=i-1的时候,3.当j=i时
1.当j<i-1的时候，由我们子结构的定义可得点i-1一定在(i,j)上且从1出发向右的时候结尾一定是j，所以与i相邻的点一定是i-1，则(i,j)=(i-1,j)+dis(i-1,i).
2.当j=i-1的时候,与i相邻的点可以是1-i-1中的任意一个点（不包括i-1),因为最后要返回i-1且并不能确定哪一条路是最短的。则(i,j)=min{(k,j)+dis(i,k)}.
3.当j=i的时候，路径上最后两个相邻的点可以是1,2,3…..i-1中的任意一个点与i.则(i,i)=min{dis(i,1)+(i,1),dis(i,2)+(i,2),……,dis(i,i-1)+(i,i-1)}.
AC代码
1168K/0MS1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<algorithm>
#include<math.h>
#include<string.h>
#include<string.h>
#include <iomanip>
using namespace std;
double dp[1000][1000];///用于记录两个点之间的最短路径
//double tp[1000][1000];
struct node
{
double x,y;
};
node point[10000];
double cmp(node a,node b)
{
if(a.x!=b.x)
return a.x<b.x;
else return a.y<b.y;
}
double distint(node a,node b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
int main()
{
/*while(1)
{
double a,b;
double c,d;
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
printf("%.2lf\n",sqrt((a-c)*(a-c)+(b-d)*(b-d)));
}*/
int n;
while(scanf("%d",&n)!=EOF)
{
memset(point,0,sizeof(point));
for(int i=1; i<=n; i++)
{
//scanf("%lf%lf",&point[i].x,&point[i].y);
cin>>point[i].x>>point[i].y;
}
sort(point,point+n,cmp);
dp[1][2]=distint(point[1],point[2]);
for (int j = 3; j <= n; ++j)
{
for (int i = 1; i <= j - 2; i++)///i<j-1的时候，b[i][j]=b[j][i-1]+dis(i-1,i);
{
dp[i][j] = dp[i][j - 1] + distint(point[j-1],point[j]);
}
dp[j-1][j]=999999;
for (int k = 1; k <= j - 2; k++)///查找最短的距离，当j=i-1的时候。。i = j - 1,dp[i][j] = min(dp[k][j - 1] + dis(k,j));
{
if(dp[k][j - 1] + distint(point[k],point[j])<dp[j-1][j])
dp[j - 1][j] = dp[k][j - 1] + distint(point[k],point[j]);
}
}
dp[n][n]=dp[n-1][n]+distint(point[n-1],point[n]);
//printf("%.2lf\n",dp[n][n]);
cout.setf(ios::fixed);
cout<<setprecision(2)<<dp[n][n]<<endl;
}
}