稻花香里说丰年,听取WA声一片
查看原帖
稻花香里说丰年,听取WA声一片
1030096
simon_only楼主2023/7/6 15:58
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n;
double d[N],ans;
bool v[N];
double a[N],b[N];
double getd(double x1,double y1,double x2,double y2){
    return sqrt((x1-y2)*(x1-x2)+(y1-y2)*(y1-y2));
}
void prim(){
    for(int i=1;i<=n;i++)
        d[i]=1e12*1.0;
    memset(v,0,sizeof(v));
    d[1]=0.0;
    for(int i=1;i<=n;i++){
        int t=0;
        for(int j=1;j<=n;j++)
            if(!v[j]&&(t==0||d[j]<d[t]))
                t=j;
        v[t]=1;
        for(int y=1;y<=n;y++)
            if(!v[y])   d[y]=min(d[y],getd(a[t],b[t],a[y],b[y]));
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++)   cin>>a[i]>>b[i];
    prim();
    for(int i=2;i<=n;i++){
        ans+=d[i];
    }
    printf("%.2lf",ans);
    return 0;
}
2023/7/6 15:58
加载中...