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;
}

提交记录