1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| const double INF=0x3f3f3f3f;
const int MAX= 5000+5;
int n,vis[MAX];
double x[MAX],y[MAX],g[MAX][MAX],low[MAX],ans=0.0;
double dis(int i,int j){
return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
}
bool prim(){
mem(vis,0);
vis[0]=1;
fi(i,1,n)low[i]=dis(0,i);
fi(i,1,n){
double _min=INF;
int k=-1;
fi(j,0,n)
if(!vis[j]&&_min>low[j]){
_min=low[j];
k=j;
}
if(_min==INF)return false;
ans += _min;
vis[k]=1;
fi(j,0,n){
double tmp=dis(k,j);
if(!vis[j]&&low[j]>tmp)
low[j]=tmp;
}
}
return true;
}
int main(){
freopen("in","r",stdin);
sf(n);
fi(i,0,n){
scanf("%lf%lf",&x[i],&y[i]);
}
prim();
printf("%.2lf",ans);
return 0;
}
|