比赛 |
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;
}