P1265-公路修建

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 #define pb push_back
 4 #define _for(i,a,b) for(int i = (a);i < (b);i ++)
 5 #define INF 100000003
 6 #define ll long long
 7 inline ll read()
 8 {
 9     ll ans = 0;
10     char ch = getchar(), last = ‘ ‘;
11     while(!isdigit(ch)) last = ch, ch = getchar();
12     while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - ‘0‘, ch = getchar();
13     if(last == ‘-‘) ans = -ans;
14     return ans;
15 }
16 inline void write(ll x)
17 {
18     if(x < 0) x = -x, putchar(‘-‘);
19     if(x >= 10) write(x / 10);
20     putchar(x % 10 + ‘0‘);
21 }
22 
23 double mincost[5003];
24 bool used[5003];
25 
26 int V;
27 struct P
28 {
29     int x;
30     int y;
31 };
32 P a[5003];
33 double cal(P a,P b)
34 {
35     return sqrt((double)(a.x-b.x)*(a.x-b.x)+(double)(a.y-b.y)*(a.y-b.y));
36 }
37 double MST()
38 {
39     _for(i,1,V+1)
40     {
41         mincost[i] = INF;
42         used[i] = false;
43     }
44 
45     mincost[1] = 0;
46     double res = 0;
47 
48     while(1)
49     {
50         int v = -1;
51         _for(u,1,V+1)
52         if(!used[u] && (v==-1 || mincost[u] < mincost[v]))
53             v = u;
54 
55         if(v==-1) break;
56         used[v] = true;
57         res += mincost[v];
58 
59         _for(u,1,V+1)
60             mincost[u] = min(mincost[u],cal(a[v],a[u]));
61     }
62     return res;
63 }
64 
65 int main()
66 {
67     V = read();
68     _for(i,1,V+1)
69         a[i].x = read(),a[i].y = read();
70     
71     printf("%.2lf\n",MST());
72     return 0;
73 }