蒟蒻10pts求助
查看原帖
蒟蒻10pts求助
1128559
guoguo160楼主2024/12/5 21:35
#include <bits/stdc++.h>

#define int long long 

using namespace std;

const int N=5010;

double x[N],y[N];
bool use[N];
double dis[N];
double ans;
int n;

double dist(double u,double v,double x,double y){
    return sqrt((u-x)*(u-x)+(v-y)*(v-y));
}

void readin() {
    cin>>n;
    for(int i=1;i<=n;++i){
        cin>>x[i]>>y[i];
        dis[i]=(1ll<<60)*1.0;
    }
    return;
}

void prim() {
    dis[1]=0;
    int min_place=0;
    double min_dist=(1ll<<60)*1.0;
    for(int j=1;j<=n;++j){
        min_place=1;
        min_dist = (1ll << 60) * 1.0;
        for (int i = 1;i <= n;++i) {
            if(!use[i]&&min_dist>dis[i]) min_dist=dis[i],min_place=i; 
        }
        use[min_place] = 1;
        ans += min_dist;
        for (int i = 1;i <= n;++i) {
            dis[i] = min(dis[i], dist(x[i], y[i], x[j], y[j]));
        }
    }
    printf("%.2lf\n",ans);
}

signed main() {
    readin();
    prim();
    return 0;
}

只能过第一个点,大佬求助

2024/12/5 21:35
加载中...