#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
#define MAXV 1005
#define INF 1e12
const int start = 1;
bool visit[MAXV] = { false };
double dist[MAXV];
int preNode[MAXV];
int vertex_size;
int road_size;
double graph[MAXV][MAXV];
struct Point{
double x;
double y;
};
Point pointArr[MAXV];
double calDist( Point a, Point b ){
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
void prim(){
double res = 0.0;
int nextIndex;
int temp_node_num = vertex_size;
for( int index = 1; index <= vertex_size; ++index ){
dist[index] = graph[1][index];
}
for( int count_num = 1; count_num <= vertex_size; ++count_num ){
double minDistance = INF;
int i;
for( i = 1; i <= vertex_size; ++i ){
if( minDistance > dist[i] && !visit[i] ){
minDistance = dist[i];
nextIndex = i;
}
}
visit[nextIndex] = true;
// cout<<nextIndex<<" "<<preNode[nextIndex]<<" "<<graph[nextIndex][preNode[nextIndex]]<<endl;
//if( graph[nextIndex][preNode[nextIndex]] != -1 ) res += graph[nextIndex][preNode[nextIndex]];
for( i = 1; i <= vertex_size; ++i ){
if( graph[nextIndex][i] < dist[i] && !visit[i] ){
dist[i] = graph[nextIndex][i];
//preNode[index] = nextIndex;
}
}
}
for( int i = 1; i <= vertex_size; ++i ){
if( dist[i] != -1 ) res += dist[i];
}
printf( "%.2lf\n", res );
}
void init(){
cin>>vertex_size>>road_size;
int i, j;
for( i = 1; i <= vertex_size; ++i ){
cin>>pointArr[i].x>>pointArr[i].y;
}
for( i = 1; i <= vertex_size; ++i ){
for( j = 1; j <= vertex_size; ++j ){
graph[i][j] = graph[j][i] = calDist( pointArr[i], pointArr[j] );
}
}
for( i = 1; i <= road_size; ++i ){
int startPoint, endPoint;
cin>>startPoint>>endPoint;
graph[startPoint][endPoint] = -1;
graph[endPoint][startPoint] = -1;
}
}
int main(){
init();
prim();
return 0;
}
POJ 3625 Building Road(Prim)