记录编号	193180	评测结果	AAAAAAAAAA
题目名称	公路修建	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.635 s
提交时间	2015-10-14 07:26:51	内存使用	0.43 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#define sqr(x) (x)*(x)
struct dd{
	double x,y;
}jie[5006];
int n;
double data=0,f[5003];
bool vis[5003];
inline double Get_dis(int i,int j) {
    return sqrt(sqr(jie[i].x-jie[j].x)+sqr(jie[i].y-jie[j].y));
}
void work(int s){
	int Min=-1;
	int sum=0;
	for(int i=1;i<=n;i++) f[i]=Get_dis(s,i);
	vis[s]=1,sum=1,f[s]=0;
	double temp;
	while(sum<n){
		Min=-1;
		for(int i=1;i<=n;i++){
		    if(vis[i]) continue;
			if(Min==-1||f[i]<f[Min]) Min=i;
		}
		if(Min==-1) break; sum++;
		vis[Min]=1;
		data+=f[Min];
		for(int i=1;i<=n;i++){
			if(vis[i]) continue;
			temp=Get_dis(Min,i);
			if(temp<f[i]) f[i]=temp;
		}
	}
}
int main(){
	freopen("roadz.in","r",stdin);
	freopen("roadz.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lf%lf",&jie[i].x,&jie[i].y);
	work(1);
	printf("%.2lf",data);
	getchar();getchar();
}