记录编号	56502	评测结果	AAAAAAAAAA
题目名称	公路修建	最终得分	100
用户昵称	QhelDIV	是否通过	通过
代码语言	C++	运行时间	1.619 s
提交时间	2013-03-31 10:00:15	内存使用	3.37 MiB

//prime
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <memory.h>
#include <cmath>
#define F_I "roadz.in"
#define F_O "roadz.out"
using namespace std;
ifstream fin(F_I);
ofstream fout(F_O);
const int Vn_Max=5001;
const double Inf=123456789.0;
int En,Vn;
/*
class Edge
{
public:
	short int u,v;
	double w;
}E[Vn_Max*Vn_Max];*/
class Node{
public:
	long long x,y;
}V[Vn_Max];
void init()
{
int i,j;
	fin>>Vn;
	for(i=1;i<=Vn;i++)
		fin>>V[i].x>>V[i].y;
	/*
	for(i=1;i<=Vn;i++)
		for(j=i+1;j<=Vn;j++)
		{
			E[++En].u=i;
			E[En].v=j;
			E[En].w=double(sqrt(double( (V[i].x-V[j].x)*(V[i].x-V[j].x)+(V[i].y-V[j].y)*(V[i].y-V[j].y))));
		}
	*/
}
class UFSet{
public:
	short Prev[Vn_Max];
	UFSet(){for(int i=1;i<Vn_Max;i++)Prev[i]=i;}
	short fr(short o)
	{
		if(Prev[o]!=o)
			Prev[o]=fr(Prev[o]);
		return Prev[o];
	}
	void Union(short a,short b)
	{
	short ra=fr(a),rb=fr(b);
		Prev[rb]=ra;
	}
}UFS;
/*
bool Cmp(Edge a,Edge b){
	return a.w<b.w;
}
void K(){
double Ans=0.0;
	sort(E+1,E+En+1,Cmp);
	for(int i=1;i<=En;i++)
	{
		if(UFS.fr(E[i].u)!=UFS.fr(E[i].v))
		{
			UFS.Union(E[i].u,E[i].v);
			Ans+=E[i].w;
		}
	}
	fout<<setiosflags(ios::fixed)<<setprecision(2)<<Ans<<endl;
}
*/
double D(int a,int b){
	return sqrt(double((V[a].x-V[b].x)*(V[a].x-V[b].x) + (V[a].y-V[b].y)*(V[a].y-V[b].y)));
}
void P(){
double d[Vn_Max],Ans=0.0;
bool flag[Vn_Max]={0};
	d[1]=0;
	for(int i=2;i<=Vn;i++)
		d[i]=Inf;
	for(int i=1;i<=Vn;i++)
	{
	double Min=Inf;
	int Mp=0;
		for(int j=1;j<=Vn;j++)	
			if(!flag[j] && Min>d[j])
			{
				Min=d[j];
				Mp=j;
			}
		flag[Mp]=true;
		Ans+=Min;
		for(int j=1;j<=Vn;j++)
			if(!flag[j])
				d[j]=min(d[j],D(Mp,j));
	}
	fout<<setiosflags(ios::fixed)<<setprecision(2)<<Ans<<endl;
}
int main()
{
	init();
	
	//K();
	P();
	
	fin.close();
	fout.close();
	return 0;
}