题目链接
1 #include <bits/stdc++.h>
2 # define LL long long
3 using namespace std;
4
5 const int maxn=5000+10;
6 int n;
7 LL dis[maxn];
8 int complete[maxn];
9
10 struct City{
11 LL x,y;
12 }cities[maxn];
13
14 LL operator*(City &c1, City &c2){
15 return (c1.x-c2.x)*(c1.x-c2.x)+(c1.y-c2.y)*(c1.y-c2.y);
16 }
17
18 int main(){
19 scanf("%d", &n);
20 for(int i=1;i<=n;++i){
21 scanf("%lld %lld", &cities[i].x, &cities[i].y);
22 }
23 memset(dis,127,sizeof(dis));
24 dis[1]=0;
25 for(int i=1;i<=n-1;++i){
26 int u=0;
27 for(int j=1;j<=n;++j){
28 if(complete[j]==1) continue;
29 if(u==0) u=j;
30 else{
31 if(dis[j]<dis[u]) u=j;
32 }
33 }
34 complete[u]=1;
35 for(int j=1;j<=n;++j){
36 if(complete[j]==1) continue;
37 dis[j]=min(dis[j],cities[u]*cities[j]);
38 }
39 }
40 double res=0;
41 for(int i=1;i<=n;++i){
42 res+=sqrt((double)dis[i]);
43 }
44 printf("%.2f", res);
45 return 0;
46 }