prim算法求最小生成树C++

以下是使用C++实现Prim算法求最小生成树的代码：

#include<bits/stdc++.h>
using namespace std;

const int N=1e5+10;
const int inf=0x3f3f3f3f;

int n,m;
int head[N],ver[N<<1],edge[N<<1],nxt[N<<1],tot;
int dis[N],vis[N];

void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,nxt[tot]=head[x],head[x]=tot;
    ver[++tot]=x,edge[tot]=z,nxt[tot]=head[y],head[y]=tot;
}

void prim()
{
    memset(dis,inf,sizeof(dis));
    dis[1]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
    q.push(make_pair(0,1));
    while(!q.empty())
    {
        int x=q.top().second;q.pop();
        if(vis[x]) continue;
        vis[x]=1;
        for(int i=head[x];i;i=nxt[i])
        {
            int y=ver[i],z=edge[i];
            if(dis[y]>z&&!vis[y])
            {
                dis[y]=z;
                q.push(make_pair(dis[y],y));
            }
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    prim();
    int ans=0;
    for(int i=1;i<=n;i++) ans+=dis[i];
    printf("%d\n",ans);
    return 0;
}

其中，`tot`表示边的编号，`head[i]`表示以节点i为起点的边的编号，`dis[i]`表示点i到最小生成树的距离，`vis[i]`表示点i是否已经加入了最小生成树。优先队列`q`用于存储当前距离最小的点。