先放一个没有优化的代码：

#include<bits/stdc++.h>
using namespace std;
int n;
bool vis[5001];
double ans;
struct s{
	double x,y;
}a[5001];
struct Node{
	int u;
	double w;
	friend bool operator < (Node x,Node y){
		return x.w>y.w; 
	}
};
priority_queue <Node> q;
void Prim(){
	q.push({1,0});
	while(!q.empty()){
		Node e=q.top();
		q.pop();
		if(vis[e.u])	continue;
		vis[e.u]=1;
		ans+=e.w;
		for(int i=1;i<=n;i++){
			if(vis[i])	continue;
			q.push({i,sqrt((a[i].x-a[e.u].x)*(a[i].x-a[e.u].x)+(a[i].y-a[e.u].y)*(a[i].y-a[e.u].y))});
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%lf%lf",&a[i].x,&a[i].y);
	Prim();
	printf("%.2f",ans);
    return 0;
}

以上代码会在#2 #9 #10三个点上MLE。

我们发现MLE是因为优先队列内存的过多导致的。

我们可以用一个 dis 数组，存优先队列内这个点离被标记过的点的最近距离，初始化成正无穷，如果发现这个的点的距离超过了它在 dis 内的值，就跳过这个点，这保证优先队列内的数不会超过 $n$。

于是我们就可以过掉本题，这里放一下代码：

#include<bits/stdc++.h>
using namespace std;
int n,vis[5001],dis[5001];
double ans;
struct s{
	double x,y;
}a[5001];
struct Node{
	int u;
	double w; 
	friend bool operator < (Node x,Node y){
		return x.w>y.w; 
	}
};
priority_queue <Node> q;
void Prim(){
	memset(dis,0x3f,sizeof(dis));
	q.push({1,0});
	while(!q.empty()){
		Node e=q.top();
		q.pop();
		if(vis[e.u])	continue;
		vis[e.u]=1;
		ans+=e.w;
		for(int i=1;i<=n;i++){
			if(vis[i]||sqrt((a[i].x-a[e.u].x)*(a[i].x-a[e.u].x)+(a[i].y-a[e.u].y)*(a[i].y-a[e.u].y))>dis[i])	continue;
			dis[i]=sqrt((a[i].x-a[e.u].x)*(a[i].x-a[e.u].x)+(a[i].y-a[e.u].y)*(a[i].y-a[e.u].y));
			q.push({i,sqrt((a[i].x-a[e.u].x)*(a[i].x-a[e.u].x)+(a[i].y-a[e.u].y)*(a[i].y-a[e.u].y))});
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%lf%lf",&a[i].x,&a[i].y);
	Prim();
	printf("%.2f",ans);
    return 0;
}

如果有帮助就关注一下楼主吧，谢谢！