双调旅行售货员问题.txt

算法设计与分析源代码算法设计与分析源代码

#include<iostream> 
#include<algorithm> 
#include<math.h> 
using namespace std; 
class point 
{ public: 
int x,y; 
}; 
int less(point &a,point &b) 
{ 
return a.x<b.x; 
} 
double sum[31][31],ind[31][31]; 
void main() 
{ 
int n,j; 
cin>>n; 
point *w=new point [n+1]; 
double t,*way=new double [n+1]; 

for(int i=1;i<=n;i++) 
cin>>w[i].x>>w[i].y; 
sort(w+1,w+n+1,less); 
for(i=1;i<=n;i++) 
{ 
for(j=i;j<=n;j++) 
if(j!=i) 
ind[i][j]=sqrt(pow(w[j].x-w[i].x,2)+pow(w[j].y-w[i].y,2)); 
else 
ind[i][j]=0; 

} 
sum[1][1]=0; 
for(i=2;i<=n;i++) 
{ sum[i-1][i]=ind[i-1][i]; 
sum[i][i]=0; 
} 
for(i=3;i<=n;i++) 
{  
for(j=1;j<=n-i+1;j++) 
sum[j][j+i-1]=sum[j][j+i-2]+ind[j+i-2][j+i-1]; 
} 


way[2]=ind[1][2]*2; 

way[1]=0; 
for(i=3;i<=n;i++) 
{ double min=10000000; 
for(j=1;j<=i-2;j++) 
{ 
  
 t=ind[j][i]+sum[j+1][i]+way[j+1]-ind[j][j+1]; 
 if(t<min) 
 min=t; 
} 
way[i]=min; 
} 
cout<<way[n]<<endl; 

}