AOJ2224.cpp

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <cmath>
#include <queue>
#include <iomanip>
#include <algorithm>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (X).begin(),(X).end()

using namespace std;

struct UnionFind {
  vector<int> parent;
  UnionFind (int n) { parent.assign(n, -1); }
  int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
  bool merge(int x, int y) {
    x = root(x); y = root(y);
    if (x == y) return false;
    if (parent[y] < parent[x]) swap(x, y);
    if (parent[x] == parent[y]) --parent[x];
    parent[y] = x;
    return true;
  }
};

typedef double Weight;
struct Edge{
  int src, dest; Weight weight;
  bool operator < (const Edge &rhs) const {return weight > rhs.weight;}
};

typedef vector<Edge> Edges;

double kruskal(int N, Edges &es) {
  sort(es.begin(), es.end());
  UnionFind uf(N);
  double res = 0;
  REP(i, es.size()) {
    Edge e = es[i];
    if(uf.root(e.src) != uf.root(e.dest)) {
      uf.merge(e.src, e.dest);
      res += e.weight;
    }
  }
  return res;
}

double dist(double x, double y) {
  return sqrt(x * x + y * y);
}

int main() {
  int n, m, v, w;
  cin >> n >> m;
  vector<double> x(n), y(n);
  REP(i,n) cin >> x[i] >> y[i];
  Edges es;
  double sum = 0;
  REP(i,m) {
    cin >> v >> w; --v; --w;
    double d = dist(x[v]-x[w], y[v]-y[w]);
    es.push_back((Edge){v, w, d});
    sum += d;
  }
  cout << setprecision(10) << fixed << sum - kruskal(n, es) << endl;
  return 0;
}