记录编号	246358	评测结果	AAAAAAAAAA
题目名称	[USACO Dec07] 建造路径	最终得分	100
用户昵称	Riolu	是否通过	通过
代码语言	C++	运行时间	0.416 s
提交时间	2016-04-05 21:55:55	内存使用	7.98 MiB

/*=========================================*
  * Auther: Riolu
  * PID: 150
  * Time: 2016.4.4
  * ©Copyright 2016 Riolu. All Rights Reserved.
  *=========================================*/
#include <cstdio>
#include <string>
#include <iostream>
#include<vector>
#include<cmath>
#define N 1001
using namespace std;
int n,m,i,j,k,tx,ty,cn=0;
struct node{int x,y;}e[N];

double dis[N],minn,sum=0;
int book[N];
double c[N][N];
int main(){
	freopen("roads.in","r",stdin);
	freopen("roads.out","w",stdout);
	cin>>n>>m;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			c[i][j]=-1;

	for(i=1;i<=n;i++)
		scanf("%d%d",&e[i].x,&e[i].y);
		
	for(i=1;i<=m;i++)
	{scanf("%d%d",&tx,&ty);c[tx][ty]=0;c[ty][tx]=0;}
	for(i=1;i<=n;i++)
		for(j=i+1;j<=n;j++)
			if(c[i][j]==-1){
				double tx=e[i].x-e[j].x,ty=e[i].y-e[j].y;
			c[i][j]=pow(tx*tx+ty*ty,0.5);
			c[j][i]=c[i][j];
			}
	/*for(i=1;i<=n;i++){
		for(j=1;j<=n;j++)
			cout<<c[i][j]<<" ";
			cout<<endl;
		}*/
		///long double kk=1000000;
	//cout<<sqrt(kk*kk*2)<<endl;
	for(i=1;i<=n;i++)
		dis[i]=c[1][i];
	book[1]=1;
	
	cn++;
	while(cn<n){
		minn=99999999;
		for(i=1;i<=n;i++){
			if(book[i]==0&&dis[i]<minn)
			{minn=dis[i];j=i;}
			}
		book[j]=1;
		cn++;
		sum+=dis[j];		
		for(k=1;k<=n;k++)
			if(book[k]==0&&dis[k]>c[j][k])
				dis[k]=c[j][k];
		}
	
	printf("%.2lf",sum);
	}