Farmer John had just acquired several new farms! He wants to connect the farms with roads so that he can travel from any farm to any other farm via a sequence of roads; roads already connect some of the farms.

Each of the N (1 ≤ N ≤ 1,000) farms (conveniently numbered 1..N) is represented by a position (X_i, Y_i) on the plane (0 ≤ X_i ≤ 1,000,000; 0 ≤ Y_i ≤ 1,000,000). Given the preexisting M roads (1 ≤ M ≤ 1,000) as pairs of connected farms, help Farmer John determine the smallest length of additional roads he must build to connect all his farms.

* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Two space-separated integers: X_i and Y_i 
* Lines N+2..N+M+2: Two space-separated integers: i and j, indicating that there is already a road connecting the farm i and farm j.

* Line 1: Smallest length of additional roads required to connect all farms, printed without rounding to two decimal places. Be sure to calculate distances as 64-bit floating point numbers.

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <string> 5 #include <cmath> 6 #include <iomanip> 7 using namespace std; 8 #define maxn 1010 9 double mp[maxn][maxn];10 int N, M;11 int vis[maxn];12 double low[maxn];13 struct Point{14     double x,y;15 }p[maxn];16 #define INF 9999999917 double cal(double x1, double y1, double x2, double y2){18     return ( sqrt( (x1-x2)*(x1-x2) +(y1-y2)*(y1-y2)));19 }20 double prime(){21     double result;int pos;22     memset(vis, 0, sizeof(vis));23     pos = 1; vis[1] = 1; low[1] = 0;24     for(int i = 1; i <= N; i++){25         if(i != pos ) low[i] = mp[1][i];  26     }27     for(int i = 1; i <= N-1; i++){28         double min = INF;29         for(int j = 1; j <= N; j++){30             if(low[j] < min && !vis[j]){31                 min = low[j];32                 pos = j;33             }34         }35         result += min;36         vis[pos] = 1;37         38         for(int j = 1; j <= N; j++){39             if(!vis[j] && mp[pos][j] < low[j]) low[j] = mp[pos][j];40         }41     }42     return result;43     44 }45 int main(){46     while(~scanf("%d%d", &N, &M)){47         memset(mp, 0, sizeof(mp));48         for(int i = 1; i <= N; i++){49             scanf("%lf%lf", &p[i].x, &p[i].y);50         }51         for(int i = 1; i <= N; i++){52             for(int j = 1; j <= N; j++){53                 if(i != j){54                     mp[i][j] = mp[j][i] = cal(p[i].x, p[i].y,p[j].x, p[j].y);55                 }56             }57         }58         for(int i = 1; i <= M; i++){59             int t1, t2;60             scanf("%d%d", &t1, &t2);61             mp[t1][t2] = mp[t2][t1] = 0;62         }63         cout<<fixed<<setprecision(2)<<prime()<<endl;64     //    printf("%lf\n", prime());65     }66     67     return 0;68 }