洛谷 1265
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<string> #include<cmath> #include<vector> #define pow1(x) (x)*(x) using namespace std; int n; double zx[5009],zy[5009],dis[5009],ans=0; bool vis[5009]; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { double x,y; scanf("%lf%lf",&x,&y); zx[i]=x,zy[i]=y; } vis[1]=true; for(int i=1;i<=n;i++) dis[i]=sqrt(pow1(zx[1]-zx[i])+pow1(zy[1]-zy[i])); for(int k=1;k<=n-1;k++) { int kk;double minn=1e10; for(int i=1;i<=n;i++) { if(!vis[i]&&dis[i]<minn) minn=dis[i],kk=i; } ans+=minn; vis[kk]=true; for(int i=1;i<=n;i++) { double len=sqrt(pow1(zx[kk]-zx[i])+pow1(zy[kk]-zy[i])); if(!vis[i]&&len<dis[i]) { dis[i]=len; } } } printf("%.2lf",ans); return 0; }