记录编号	457988	评测结果	AAAAAAAAAA
题目名称	[USACO Dec07] 建造路径	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.380 s
提交时间	2017-10-09 21:28:45	内存使用	23.66 MiB

#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=1010;
struct poi{
	double x,y;
}p[maxn];
int n,m,tot,v[maxn*maxn],u[maxn*maxn],r[maxn*maxn],f[maxn],map[maxn][maxn];
double ans,w[maxn*maxn];
bool cmp(int x,int y){return w[x]<w[y];}
int find(int x){
	if(f[x]!=x)f[x]=find(f[x]);
	return f[x];
}
void kruskal(){
	sort(r+1,r+1+tot,cmp);
	for(int i=1;i<=tot;i++){
		int e=r[i];
		int f1=find(u[e]),f2=find(v[e]);
		if(f1!=f2)ans+=w[e],f[f1]=f2;
	}	
}
int main(){
	freopen("roads.in","r",stdin);
	freopen("roads.out","w",stdout);
	scanf("%d%d",&n,&m);
	int a,b;
	for(int i=1;i<=n;i++)scanf("%lf%lf",&p[i].x,&p[i].y);
	for(int i=1;i<=m;i++)scanf("%d%d",&a,&b),map[a][b]=map[b][a]=1;
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			double dis=sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));
			tot++,u[tot]=i,v[tot]=j,r[tot]=tot;
			if(!map[i][j])w[tot]=dis;
			else w[tot]=0;
		}
	}
	for(int i=1;i<=n;i++)f[i]=i;
	kruskal();
	printf("%.2lf\n",ans);
	return 0;
}