算法导论-15-1-双调欧几里得旅行商问题题目：思考：可以把题目看作是从最左点到最右点的不重叠不相交的两条
算法导论-15-1-双调欧几里得旅行商问题
题目：
思考：
可以把题目看作是从最左点到最右点的不重叠不相交的两条路径，求这两条路径的和最短。
对所有点按x坐标排序，从0开始标记顺序。
令两条路径分另为A和B，从是0开始。令A[i]表示A从0出发严格向右到i的路径，B[j]表示B从0出发严格向右到j的路径。d[i][j]为点i与点j之间的距离。s[i][j]为满足以下条件的A[i]和B[j]的路径和的最小长度：(1)0<=i<=j<n(2)路径包含了0-j的所有的点(3)两个路径没有重复（除了0）的点。
根据以上定义得到的s[i][j]满足以下性质：(1)s[i][j]=s[j][i](2)当j=i时，s[i][j]=s[i][i]=s[i][i-1]+d[i-1][i](2)当j=i+1时,s[i][j]=MIN(s[i][k]+d[k][j])，其中0<=k<i(3)当j>i+1时，s[i][j]=s[i][j-1]+d[j-1][j]。这些性质画图即可推出，不证明。
程序不复杂，根据以上公式对照写出
代码：
#include <iostream>#include <algorithm>#include <cmath>using namespace std;//点的个数#define N 7struct node{int x;int y;}s[N];//用于排序bool cmp(node a, node b){return a.x < b.x;}//计算d[i][j]double dis(int i, int j){double temp = pow((s[i].x-s[j].x)*1.0, 2) + pow((s[i].y-s[j].y)*1.0, 2);return sqrt(temp);}/*1 1 2 73 46 37 68 29 5*/int main(){int i, j;//输出测试数据，从0开始编号for(i = 0; i < N; i++)cin>>s[i].x>>s[i].y;//根据x从小到大排序sort(s, s+N, cmp);double ans[N][N] = {0};for(i = 0; i < N; i++){//s[0][0]=0//当j=i时，s[i][j]=s[i][i]=s[i][i-1]+d[i-1][i]if(i)ans[i][i] = ans[i][i-1] + dis(i-1, i);//当j=i+1时,s[i][j]=MIN(s[i][k]+d[k][j])，其中0<=k<idouble min = 0x7fffffff, temp;if(i){for(j = 0; j < i; j++){temp = ans[i][j] + dis(j, i+1);if(temp < min)min = temp;}}//s[0][1]=d[0][1]else min = dis(0, 1);//s[i][j]=s[j][i]ans[i][i+1] = min;ans[i+1][i] = min;//当j>i+1时，s[i][j]=s[i][j-1]+d[j-1][j]for(j = i + 2; j < N; j++){//s[i][j]=s[j][i]ans[i][j] = ans[i][j-1] + dis(j-1, j);ans[j][i] = ans[i][j];}}/*输出矩阵sfor(i = 0; i < N; i++){for(j = 0; j < N; j++)cout<<ans[i][j]<<' ';cout<<endl;}*///输出结果cout<<ans[N-1][N-1]<<endl;return 0;}