比赛 |
20181007 |
评测结果 |
AAAAAAAAAA |
题目名称 |
建造路径 |
最终得分 |
100 |
用户昵称 |
梦那边的美好ET |
运行时间 |
0.569 s |
代码语言 |
C++ |
内存使用 |
18.43 MiB |
提交时间 |
2018-10-06 18:38:29 |
显示代码纯文本
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
using namespace std;
struct hs{double l;int x,y;}d[1000010];
int a[1010],b[1010],fa[1010],n,m,a1,a2,sum=0;
double ans=0.0;
int find(int p){return fa[p]=(fa[p]==p)?p:find(fa[p]);}
bool bk(hs p1,hs p2){return p1.l<p2.l;}
int main(){
freopen("roads.in","r",stdin);
freopen("roads.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++)scanf("%d%d",&a[i],&b[i]);
if(m)for(int i=1;i<=m;i++){
scanf("%d%d",&a1,&a2);
int f1=find(a1),f2=find(a2);
if(f1==f2)continue;
fa[f2]=f1;
}
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
int f1=find(i),f2=find(j);
if(f1==f2)continue;
d[++sum].x=i;d[sum].y=j;
d[sum].l=(double)sqrt((double)(a[i]-a[j])*(a[i]-a[j])+(double)(b[i]-b[j])*(b[i]-b[j]));
}
}
sort(d+1,d+1+sum,bk);
for(int i=1;i<=sum;i++){
int f1=find(d[i].x),f2=find(d[i].y);
if(f1==f2)continue;
fa[f2]=f1;ans+=d[i].l;
}
printf("%.2f",ans);
return 0;
}