SRM503 Div2 Hard

900
MST

class KingdomXCitiesandVillagesAnother {
public:
  double etermineLength(vector <int> cX, vector <int> cY, vector <int> vX, vector <int> vY)
  {
    const int C = cX.size();
    const int V = vX.size();

    bool vis[V];   
    fill(vis, vis + V, false);

    double cost[V];
    fill(cost, cost + V, 1e256);

    for (int v = 0; v < V; ++v) {
      for (int c = 0; c < C; ++c) {
        double x = cX[c] - vX[v];
        double y = cY[c] - vY[v];
        cost[v] = min(cost[v], sqrt(x * x + y * y));
      }
    }

    while (true) {
      double mn = 1e256;
      int idx = -1;
      for (int v = 0; v < V; ++v) {       
        if (!vis[v] && mn > cost[v]) {
          idx = v;
          mn = cost[v];
        }
      }
      if (idx == -1) break;
      vis[idx] = true;
      for (int v = 0; v < V; ++v) {
        if (vis[v]) continue;
        double x = vX[idx] - vX[v];
        double y = vY[idx] - vY[v];
        cost[v] = min(cost[v], sqrt(x * x + y * y));
      }
    }
   
    return accumulate(cost, cost + V, 0.0);
  }
};