Prim算法，用了堆优化

Code

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define PII pair<int,int>
const int N=2e5+10;
struct node{
	long long v,w;
};
vector<node>a[N];
long long n,m;
int h[N];
priority_queue<PII,vector<PII>,greater<PII> > q;
void prim(){
	int ans=0,tot=0;
	int u=1;
	h[1]=1;
	for(int j=0;j<a[u].size();j++){
		q.push(make_pair(a[u][j].w,a[u][j].v));
	}
	for(int i=1;i<n;i++){
		while(h[q.top().second])q.pop();
		u=q.top().second;
		ans+=q.top().first;
		tot++;
		if(tot==n-1) break;
		h[u]=1;
		q.pop();
		for(int j=0;j<a[u].size();j++){		
			q.push(make_pair(a[u][j].w,a[u][j].v));		
		}
	}
	if(tot==n-1) printf("%lld",ans);
	else printf("orz");
}
main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%lld%lld%lld",&u,&v,&w);
		a[u].push_back(node{v,w});
		a[v].push_back(node{u,w});
	}
	prim();
	return 0;
}

提交记录