比赛 20110318 评测结果 AAAAAAAAAA
题目名称 公路修建 最终得分 100
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-03-18 19:08:32
显示代码纯文本
#include <iostream>
#include <cmath>

using namespace std;

const int MAXN=5001;
const int oo=2000000000;

double h[MAXN],mi,x[MAXN],y[MAXN];
int n,i,j,xx,k;
bool b[MAXN];

inline double dist(int i,int j)
{
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}

void init()
{
	freopen("roadz.in","r",stdin);
	freopen("roadz.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%lf%lf",x+i,y+i);
}

void prim()
{
	for (i=2;i<=n;i++)
		h[i]=oo;
	for (xx=1;xx<n;xx++)
	{
		mi=oo;
		for (i=1;i<=n;i++)
			if (h[i]<mi && !b[i] )
			{
				mi=h[i];
				k=i;
			}
		b[k]=true;
		for (i=1;i<=n;i++)
			if (!b[i])
				if (h[i]>dist(i,k)) h[i]=dist(i,k);
	}
}

int main()
{
	init();
	prim();
	double ans=0;
	for (i=1;i<=n;i++)
		ans+=h[i];
	printf("%0.2lf\n",ans);
	return 0;
}