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

int n;

double ans,s[5001];

double x[5001],y[5001];

bool flag[5001];

inline double sqr(double a)
{return a*a;}

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

inline double min(double a,double b)
{
	return a<b?a:b;
}

int main()
{
	freopen("roadz.in","r",stdin);
	freopen("roadz.out","w",stdout);
	int i,j,k;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		s[i]=100000000;
		scanf("%lf%lf",&x[i],&y[i]);
	}
	s[0]=100000000;s[1]=0;
	for(i=1;i<=n;i++)
	{
		k=0;
		for(j=1;j<=n;j++)
		{
			if(!flag[j]&&s[j]<s[k])k=j;
		}
		flag[k]=true;ans+=s[k];
		for(j=1;j<=n;j++)
		{
			if(!flag[j])
			s[j]=min(s[j],length(j,k));
		}
	}
	printf("%.2lf\n",ans);
	return 0;
}