【模板】Prim+堆优化

#include<bits/stdc++.h>
#define MAX 5005
#define INF 0x3f3f3f3f
using namespace std;
int n,m,dis[MAX],ans=0;
bool b[MAX]={0};
struct Edge
{
    int id,c;
    Edge(int x,int y){id=x,c=y;}
    bool operator < (const Edge &other)const
    {
        return c>other.c;
    }
};
vector<Edge>G[MAX];
void Prim(int s)
{
    memset(dis,INF,sizeof dis);
    dis[s]=0;
    priority_queue<Edge>q;
    q.push(Edge(s,dis[s]));
    while(!q.empty())
    {
        Edge t=q.top();
        q.pop();
        int u=t.id;
        if(b[u])continue;
        b[u]=1;
        ans+=t.c;
        for(int i=0;i<G[u].size();i++)
        {
            int v=G[u][i].id;
            if(!b[v]&&(dis[v]>G[u][i].c))
            {
                dis[v]=G[u][i].c;
                q.push(Edge(v,dis[v]));
            }
        }
    }
}
int main()
{
    bool flag=1;
    int a1,b1,c1;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&a1,&b1,&c1);
        G[a1].push_back(Edge(b1,c1));
        G[b1].push_back(Edge(a1,c1));
    }
    Prim(1);
    for(int i=1;i<=n;i++)if(dis[i]==INF){flag=0;break;}
    if(flag)printf("%d\n",ans);
    else printf("orz\n");
    return 0;
}