比赛 HAOI2009 模拟试题3 评测结果 AAAAAAAAAA
题目名称 公路修建 最终得分 100
用户昵称 zqzas 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2009-04-23 11:22:06
显示代码纯文本
#include <iostream>
#include <math.h>

#define MAXN 5010
#define INF 1e20

int n;
double ans,dis[MAXN],x[MAXN],y[MAXN];

inline double far(int a,int b)
{
	return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}

void prim()
{
	int k,i,x,y;
	double min;
	bool isin[MAXN]={0};
	for (k=0;k<MAXN;k++)
		dis[k]=INF;
	dis[1]=0;
	for (k=1;k<=n;k++)
	{
		//getMin
		min=INF;
		for (i=1;i<=n;i++)
			if (!isin[i] && dis[i]<min)
			{
				min=dis[i];
				x=i;
			}
		isin[x]=true;
		for (y=1;y<=n;y++)
			if (!isin[y] && far(x,y)<dis[y])
				dis[y]=far(x,y);
	}
	for (i=1;i<=n;i++)
		ans+=dis[i];
}

void run()
{
	prim();
}

void ini()
{
	int i;
	scanf("%d",&n);
	for (i=1;i<=n;i++)
		scanf("%lf%lf",&x[i],&y[i]);
}

int main()
{
	freopen("roadz.in","r",stdin);
	freopen("roadz.out","w",stdout);
	ini();
	run();
	printf("%.2lf",ans);
	return 0;
}