相当丑陋的代码,还望谅解
#include <cstdio>
#include <iostream>
#include <cmath>
using namespace std;
#define ri register int
int n;
double ans[17][17];
struct NoDe{
double x;
double y;
}arr[17];
bool brr[17];
double mini=10000.0;
inline double Dist(NoDe i,NoDe j)
{
return sqrt((i.x-j.x)*(i.x-j.x)+(i.y-j.y)*(i.y-j.y));
}
inline void search(int poi,double cur,int k)
{
if(cur>mini)
{
return;
}
if(k==n)
{
if(cur<mini)
{
mini=cur;
}
return;
}
for(ri i=1;i<=n;i++)
{
if(brr[i]==0)
{
brr[i]=1;
search(i,cur+ans[poi][i],k+1);
brr[i]=0;
}
}
}
int main()
{
// freopen("card.in","r",stdin);
// freopen("card.out","w",stdout);
scanf("%d",&n);
for(ri i=1;i<=n;i++)
scanf("%lf %lf",&arr[i].x,&arr[i].y);
n++;
arr[n].x=0.0;
arr[n].y=0.0;
for(ri i=1;i<=n;i++)
for(ri j=i+1;j<=n;j++)
{
ans[i][j]=Dist(arr[i],arr[j]);
ans[j][i]=ans[i][j];
}
n--;
search(n+1,0,0);
printf("%.2lf\n",mini);
return 0;
}