UVa 10397 - Connect the Campus

// UVa 10397 - Connect the Campus

#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <stdio.h>
#include <cmath>
using namespace std;

#define integer signed long long int

struct point {
	integer x, y;
};

struct edge {
	int i, j;
	integer d;
};

bool operator <(edge a, edge b) {
	return a.d > b.d;
}

integer dist(point p1, point p2) {
	return (p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y);
}

vector<int> comp[751];
int c[751], count;

void fill(int a, int b) {
	int cb = c[b];
	for (int j = 0; j < comp[cb].size(); j++) {
		c[comp[cb][j]] = c[a];
		comp[c[a]].push_back(comp[cb][j]);
	}
	count++;
}

int main() {
	int n;
	while (cin >> n) {
		point p[751];
		for (int i = 1; i <= n; i++) {
			cin >> p[i].x >> p[i].y;
			c[i] = i;
			comp[i].clear();
			comp[i].push_back(i);
		}
		count = n;
		int m;
		cin >> m;
		for (int i = 0; i < m; i++) {
			int a, b;
			cin >> a >> b;
			if (c[a] != c[b])
				fill(a, b);
		}
		priority_queue<edge> q;
		for (int i = 1; i <= n; i++) {
			for (int j = i + 1; j <= n; j++)
				if (c[i] != c[j]) {
					edge e = { i, j, dist(p[i], p[j]) };
					q.push(e);
				}
		}
		double sol = 0;
		while (count != 1 && !q.empty()) {
			edge e = q.top();
			q.pop();
			if (c[e.i] != c[e.j]) {
				fill(e.i, e.j);
				sol += sqrt(e.d * 1.0);
			}
		}
		printf("%.2f\n", sol);
	}
	return 0;
}