求助。10pts。玄关。
查看原帖
求助。10pts。玄关。
556285
FBI_Hu_Tao楼主2024/3/31 17:00
#include<bits/stdc++.h>
using namespace std;
const double N=3e10;
struct node{
	int x,y;
}dot[5010];
struct kkk{
	double val;
	int pos;
	bool operator<(const kkk &x)const{
		return val>x.val;
	}
};
priority_queue<kkk>q;
int n,t;
double minn,ans;
double lowl[5010];
int vis[5010];
double dist(int x1,int y1,int x2,int y2){
	return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
int main(){
	cin>>n;
	//memset(lowl,0x7f,sizeof(lowl));
	for(int i=1;i<=n;i++)lowl[i]=N;
	for(int i=1;i<=n;i++)cin>>dot[i].x>>dot[i].y;
	lowl[1]=0;vis[1]=1;
	for(int i=1;i<=n;i++){
		double temp=dist(dot[1].x,dot[1].y,dot[i].x,dot[i].y);
		if(temp<lowl[i]&&vis[i]==0){
			lowl[i]=temp;
			kkk te;te.val=temp;te.pos=i;
			q.push(te);
		}
	}
	while(!q.empty()){
		minn=q.top().val;t=q.top().pos;q.pop();
		if(vis[t]==1)continue;
		vis[t]=1;
		ans+=minn;
		for(int i=1;i<=n;i++){
			double temp=dist(dot[t].x,dot[t].y,dot[i].x,dot[i].y);
			if(temp<lowl[i]&&vis[i]==0){
				lowl[i]=temp;
				kkk te;te.val=temp;te.pos=i;
				q.push(te);
			}
		}
	}
	printf("%.2lf\n",ans);
	return 0;
} 

就挺无语的。。。

2024/3/31 17:00
加载中...