记录编号 |
518675 |
评测结果 |
AAAAAAAAAA |
题目名称 |
[USACO Dec07] 建造路径 |
最终得分 |
100 |
用户昵称 |
落痕 |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.629 s |
提交时间 |
2018-10-30 20:19:40 |
内存使用 |
23.32 MiB |
显示代码纯文本
#include<bits/stdc++.h>
#define DB double
#define ll long long
using namespace std;
const ll N=1e3+2;
ll n,m,f[N],x[N],y[N];
DB get(ll a,ll b)
{
DB g=(x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]);
return sqrt(g);
}
struct node{
ll u,v;
DB c;
}e[N*N];
bool cmp(node A,node B){return A.c<B.c;}
ll F(ll x)
{
if(x==f[x]) return x;
else return f[x]=F(f[x]);
}
DB ans;
ll tot;
int main()
{
freopen("roads.in","r",stdin);
freopen("roads.out","w",stdout);
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;++i)
scanf("%lld%lld",&x[i],&y[i]),f[i]=i;
for(ll i=1,u,v;i<=m;++i)
{
scanf("%lld%lld",&u,&v);
u=F(u);v=F(v);
f[u]=v;
}
for(ll i=1;i<=n;++i)
for(ll j=i+1;j<=n;++j)
{
if(F(i)==F(j)) continue;
e[++tot]=(node){i,j,get(i,j)};
}
sort(e+1,e+tot+1,cmp);
for(ll i=1,u,v;i<=tot;++i)
{
u=F(e[i].u);v=F(e[i].v);
if(u!=v)
{
f[u]=v;ans+=e[i].c;
}
}
printf("%.2lf",ans);
return 0;
}