记录编号	9978	评测结果	AAAAAAAAAA
题目名称	公路修建	最终得分	100
用户昵称	BYVoid	是否通过	通过
代码语言	C++	运行时间	2.139 s
提交时间	2009-04-23 13:50:59	内存使用	0.35 MiB

/* 
 * Problem: HAOI2008 parterre
 * Author: Guo Jiabao
 * Time: 2009.4.23 13:33
 * State: Solved
 * Memo: 最小生成树
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
const int MAXN=5001;
const double INF=1e20;
using namespace std;
struct point
{
	int x,y;
}P[MAXN];
double mst[MAXN];
int cls[MAXN],N;
void init()
{
	freopen("roadz.in","r",stdin);
	freopen("roadz.out","w",stdout);
	scanf("%d",&N);
	for (int i=1;i<=N;i++)
		scanf("%d%d",&P[i].x,&P[i].y);
}
inline double w(int a,int b)
{
	double x=P[a].x - P[b].x,y=P[a].y - P[b].y;
	return sqrt(x*x+y*y);
}
void prim()
{
	int i,j,k;
	double Min,delta;
	for (i=1;i<=N;i++)
		mst[i]=INF;
	for (i=1;i;)
	{
		mst[i]=-INF;
		for (j=1;j<=N;j++)
			if ((delta=w(i,j))<mst[j])
			{
				mst[j]=delta;
				cls[j]=i;
			}
		Min=INF;k=0;
		for (j=1;j<=N;j++)
			if (mst[j]!=-INF && mst[j]<Min)
			{
				Min=mst[j];
				k=j;
			}
		i=k;
	}
}
void print()
{
	int i;double Ans=0;
	for (i=2;i<=N;i++)
		Ans +=w(i,cls[i]);
	printf("%.2lf\n",Ans);
}
int main()
{
	init();
	prim();
	print();
	return 0;
}