双调旅行售货员问题（动态规划）

计算机算法设计与分析3-12

#include<iostream>

#include<cmath> #include<fstream> #include<iomanip> using namespace std; ifstream fin("input3-12.txt"); ofstream fout("output3-12.txt"); double length(double x1,double y1,double x2,double y2){ double a=(x1-x2)*(x1-x2); double b=(y1-y2)*(y1-y2); return sqrt(a+b); } int main(){ int n; fin>>n; double x[n+1],y[n+1]; double p[n][n],d[n][n];//p[i][j]表示第i个点与第j个点的距离 for(int i=1;i<=n;i++){//d[i][j](i>j)表示从第i个点到第一个点再到第j个点距离 fin>>x[i]>>y[i]; } for(int i=1;i<=n;i++){//按x坐标排序 for(int j=i+1;j<=n;j++){ if(x[i]>x[j]){ swap(x[i],x[j]); swap(y[i],y[j]); } } } for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){ p[i][j]=p[j][i]=length(x[i],y[i],x[j],y[j]);//计算两点间距离 } } d[1][1]=0; for(int i=2;i<=n;i++){ d[i][1]=p[i][1]; } for(int i=2;i<n;i++){ d[i+1][i]=1000;//从第i+1个点到第一个点再回到第i个点的距离，先初始化为一个很大的值 for(int j=1;j<=i-1;j++){ d[i+1][j]=d[i][j]+p[i][i+1]; d[i+1][i]=min(d[i+1][i],d[i][j]+p[j][i+1]); } } fout<<setiosflags(ios::fixed)<<setprecision(2)<<d[n][n-1]+p[n][n-1]<<endl; return 0; }