比赛 |
20181007 |
评测结果 |
AEAEEEEEEE |
题目名称 |
建造路径 |
最终得分 |
20 |
用户昵称 |
tx_siny |
运行时间 |
0.435 s |
代码语言 |
C++ |
内存使用 |
3.19 MiB |
提交时间 |
2018-10-07 10:44:06 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;
typedef long double ld;
inline int read(){
int f=1,x=0;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-1;
ch=getchar();
}
while(isdigit(ch)){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
#define read(x) x=read()
struct Point{
int x,y;
};
Point p[maxn];
struct Line{
int x,y;
ld dis;
bool friend operator <(Line x,Line y){
return x.dis<y.dis;
}
};
int l_num;
Line l[maxn];
int m,n,f[maxn];
ld ans;
inline ld getdis(Point a,Point b){
int x=b.x-a.x;
int y=b.y-a.y;
return sqrt(x*x+y*y);
}
int father(int k){
return f[k]==k?f[k]:f[k]=father(f[k]);
}
void Init(){
read(n);read(m);
for(int i=1;i<=n;i++){
read(p[i].x);
read(p[i].y);
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
Line now;
now.x=i;now.y=j;
now.dis=getdis(p[i],p[j]);
l[++l_num]=now;
}
for(int i=1;i<=n;i++)
f[i]=i;
sort(l+1,l+l_num+1);
for(int i=1;i<=m;i++){
int x,y;
read(x);read(y);
int fx=father(x);
int fy=father(y);
if(fx==fy) continue;
f[fx]=fy;
}
}
void kruskal(){
ans=0;
for(int i=1;i<=l_num;i++){
int fx=father(l[i].x);
int fy=father(l[i].y);
if(fx==fy) continue;
ans+=l[i].dis;
f[fx]=fy;
}
}
int main(){
freopen("roads.in","r",stdin);
freopen("roads.out","w",stdout);
Init();
kruskal();
cout<<fixed<<setprecision(2)<<ans;
return 0;
}