堆优化prim,MLE70分???
查看原帖
堆优化prim,MLE70分???
984450
zhoujinhong楼主2023/12/31 23:34
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5010;
int n,vis[N];
double x[N],y[N],dis[N],sum;
struct node{
	int to;
	double w;
};
vector<node>g[N];
double jisuan(int i,int j){
	return sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
} 
priority_queue<pair<double,int> >q;
void prim(){
	for(int i=1;i<=n;i++) dis[i]=0x3f3f3f3f;
	dis[1]=0;
	q.push(make_pair(0,1));
	while(q.size()){
		int cur=q.top().second;
		q.pop();
		if(vis[cur]) continue;
		vis[cur]=1;
		for(int i=0;i<g[cur].size();i++){
			int tmp1=g[cur][i].to;
			double tmp2=g[cur][i].w;
			if(vis[tmp1]==0 && tmp2<dis[tmp1]){
				dis[tmp1]=tmp2;
				q.push(make_pair(-dis[tmp1],tmp1));
			} 
		}
	}
	for(int i=1;i<=n;i++){
		sum+=dis[i];
	}
}
signed main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=i+1;j<=n;j++){
			g[i].push_back({j,jisuan(i,j)});
			g[j].push_back({i,jisuan(i,j)});
		}
	}
	prim();
	printf("%.2lf",sum); 
	return 0;
}
2023/12/31 23:34
加载中...