如题
代码
#include<bits/stdc++.h>
using namespace std;
int n;
double dp[100001][21],a[21],b[21],ans=1e9;
bool v[21]={0};
double cd(int x,int y)
{
return sqrt((a[x]-a[y])*(a[x]-a[y])+(b[x]-b[y])*(b[x]-b[y]));
}
void dfs(int t,int now,double s,int b)
{
if (t==n)
{
ans=ans<s?ans:s;
return;
}
if (s>ans)
return;
for(int i=1;i<=n;i++)
{
if (v[i]==0)
{
int p=b+(1<<(i-1));
if (dp[p][i]!=0&&dp[p][i]<=s+cd(now,i))
continue;
v[i]==1;
dp[p][i]=s+cd(now,i);
dfs(t+1,i,dp[p][i],p);
v[i]==0;
}
}
}
int main()
{
int i;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i]>>b[i];
dfs(0,0,0,0);
printf("%0.2lf",ans);
return 0;
}