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