有 N ( <=20 ) 台 PC 放在机房内，现在要求由你选定一台 PC，用共 N-1 条网线从这台机器开始一台接一台地依次连接他们，最后接到哪个以及连接的顺序也是由你选定的，为了节省材料，网线都拉直。求最少需要一次性购买多长的网线。（说白了，就是找出 N 的一个排列 P1 P2 P3 ..PN 然后 P1 -> P2 -> P3 -> ... -> PN 找出 |P1P2|+|P2P3|+...+|PN-1PN| 长度的最小值)

第一行 N ，下面 N 行，每行分别为机器的坐标(x,y) ( 实数 -100<=x,y<=100 )

最小的长度，保留两位小数。

3
0 0
1 1
1 -1

2.83

随机化算法。

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
double x[22],y[22];

double f[22][22];
int n;
int index[22];
double dist(double x1,double y1,double x2,double y2){
       return sqrt( (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2) );
}
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]);
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        f[i][j]=dist(x[i],y[i],x[j],y[j]);
    for(int i=1;i<=n;i++){
        f[0][i]=0;
        f[i][n+1]=0;
    }
    for(int i=1;i<=n;i++) index[i]=i;
}
void sv(int a,int b)
{
    int i,j;
    for (i=a,j=b;i<=j;i++,j--)
    {
        swap(index[i],index[j]);
    }
}
double solve(){
       for(int i=1;i<=100;i++){
          int a=rand()%(n)+1;
          int b=rand()%(n)+1;
          swap(index[a],index[b]);
       }

       for(int i=1;i<=n-1;i++){
           for(int j=i+1;j<=n;j++)
           if(f[index[ i-1] ][index[i] ]+f[ index[j] ][index[j+1] ]>
              f[index[ i-1] ][index[j] ]+f[ index[i] ][index[j+1] ] ){
                 sv(i,j);
              }
       }
       double t=0;
       for(int i=1;i<=n-1;i++){
          t+=f[index[i] ][ index[i+1]];
       }
       return t;
}

int main(){
    freopen("linec.in","r",stdin);
    freopen("linec.out","w",stdout);
    init();
    double ans=100000000;
    for(int i=1;i<=2000;i++){
        double t=solve();
        if(t<ans) ans=t;
    }
    printf("%.2lf\n",ans);
    return 0;
}