我是奶龙
  • 板块灌水区
  • 楼主wzc2013
  • 当前回复7
  • 已保存回复7
  • 发布时间2024/12/1 11:59
  • 上次更新2024/12/1 14:47:53
查看原帖
我是奶龙
1491261
wzc2013楼主2024/12/1 11:59
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,m;
double x[N],y[N];
double a[N],d[N];
bool vis[N];
double dis(double x1,double y1,double x2,double y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
double PM(){
	double sum=0;
	memset(vis,false,sizeof(vis));
	for(int i=1;i<=n;i++)d[i]=1e18;
	d[1]=0;
	for(int i=0;i<n;i++){
		int u=-1;
		for(int v=1;v<=n;v++){
			if(vis[v])continue;
			if(u==-1||d[v]<d[u]){
				u=v;
			}
		}
		vis[u]=true;
		sum+=d[u];
		for(int v=1;v<=n;v++){
			if(!vis[v])d[v]=min(d[v],dis(x[u],y[u],x[v],y[v]));
		}
	}
	return sum;
}
int main(){
	cin>>n;
	for(int u=1;u<=n;u++){
		cin>>x[u]>>y[u];
	}
	cout<<fixed<<setprecision(30)<<PM();
}
2024/12/1 11:59
加载中...