记录编号	60966	评测结果	AAAAAAAAAA
题目名称	线型网络	最终得分	100
用户昵称	宋S	是否通过	通过
代码语言	C++	运行时间	5.161 s
提交时间	2013-06-01 20:34:14	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<string>
#include<algorithm>
#include<ctime>
#define p 10000
#define inf 1000000000
using namespace std;
int n;
typedef struct{double x,y;}node;
node a[30];
double w[30][30];
int ww[30][30];
int flag[30];
int s[30],t;

inline double d(int i,int j)
{
  double xx=a[i].x-a[j].x;
  double yy=a[i].y-a[j].y;
  return sqrt(xx*xx+yy*yy);
} 

inline void init()
{ 
  srand(time(NULL));
  scanf("%d",&n);
  for (int i=1; i<=n; ++i)
    scanf("%lf %lf",&a[i].x,&a[i].y);
  for (int i=1; i<=n; ++i)
    for (int j=1; j<=n; ++j)
      w[i][j]=d(i,j);
  for (int i=1; i<=n; ++i)
    {
      memset(flag,0,sizeof(flag));
      for (int j=1; j<=n; ++j)
        {
          double min_=inf;
          int u=0;
          for (int k=1; k<=n; ++k)
            if ((!flag[k]) && (w[i][k]<min_))
              {
                min_=w[i][k];
                u=k;
              }
          flag[u]=1;
          ww[i][j]=u;
        }
    }
}

inline double check()
{
  double ans=0;
  for (int i=1; i<n; ++i)
    ans+=w[s[i]][s[i+1]];
  return ans;
}

inline void work()
{
  double best=inf;
  for (int i=1; i<=n; ++i)
    {
      for (int j=1; j<=1000000/n; ++j)
        {
          memset(flag,0,sizeof(flag));
          memset(s,0,sizeof(s));
          t=1; s[1]=i; flag[i]=1;
          for (int k=2; k<=n; ++k)
            {
              int u=0;
              for (int l=1; l<=n; ++l)
                if ((!flag[ww[s[t]][l]])&&(((double)(rand()%10000)/10000)>0.2) || (l==n))
                  {u=ww[s[t]][l]; break;}
              flag[u]=1;
              s[++t]=u;
            }
          best=min(best,check());
        }
    }
  printf("%0.2lf\n",best);
}        

int main()
{
  freopen("linec.in","r",stdin);
  freopen("linec.out","w",stdout);
  init();
  work();
  return 0;
}