#邮件
2026-08-05 13:58:09
发布于：浙江
5阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int n;
double x[20];
double y[20];
double ju(int i,int j){
double xv=x[i],xx=x[j];
double yv=y[i],yy=y[j];
double X=abs(xv-xx);
double Y=abs(yv-yy);
return sqrt(X*X+Y*Y);
}
double dp[1<<15][16];
int main(){
memset(dp,1e9,sizeof dp);
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
}
for(int i=0;i<n;i++){
int j=1<<i;
dp[j][i+1]=ju(0,i+1);
}
for(int i=0;i<(1<<n);i++){
for(int j=0;j<n;j++){
int x=(i>>j)&1;
if(x==0)continue;
for(int k=1;k<=n;k++){
if((i>>(k-1)&1)==1){
double l=ju(j+1,k);
dp[i][j+1]=min(dp[i][j+1],dp[(1<<j)^i][k]+l);
}
}
}
}
double ans=1e9;
for(int i=1;i<=n;i++){
ans=min(ans,dp[(1<<n)-1][i]);
}
cout<<ans;
return 0;
}
这里空空如也
有帮助，赞一个