SRM503 Div2 Hard

900
MST

view plainprint?

1. class KingdomXCitiesandVillagesAnother {  
2. public:  
3.   double etermineLength(vector <int> cX, vector <int> cY, vector <int> vX, vector <int> vY)  
4.   {  
5.     const int C = cX.size();  
6.     const int V = vX.size();  
7.   
8.     bool vis[V];     
9.     fill(vis, vis + V, false);  
10.   
11.     double cost[V];  
12.     fill(cost, cost + V, 1e256);  
13.   
14.     for (int v = 0; v < V; ++v) {  
15.       for (int c = 0; c < C; ++c) {  
16.         double x = cX[c] - vX[v];  
17.         double y = cY[c] - vY[v];  
18.         cost[v] = min(cost[v], sqrt(x * x + y * y));  
19.       }  
20.     }  
21.   
22.     while (true) {  
23.       double mn = 1e256;  
24.       int idx = -1;  
25.       for (int v = 0; v < V; ++v) {         
26.         if (!vis[v] && mn > cost[v]) {  
27.           idx = v;  
28.           mn = cost[v];  
29.         }  
30.       }  
31.       if (idx == -1) break;  
32.       vis[idx] = true;  
33.       for (int v = 0; v < V; ++v) {  
34.         if (vis[v]) continue;  
35.         double x = vX[idx] - vX[v];  
36.         double y = vY[idx] - vY[v];  
37.         cost[v] = min(cost[v], sqrt(x * x + y * y));  
38.       }  
39.     }  
40.      
41.     return accumulate(cost, cost + V, 0.0);  
42.   }  
43. };  

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);
  }
};