Prim算法堆优化

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <set>
#include <queue>
#include <algorithm>
#define LL long long int
#define N 100000+10 //最大节点数
#define M 1000000+10 //最大的边数
#define MOD 142857
//N<=10^5, M<=10^6
 
using namespace std;
int n, m;
struct node
{
    int v, w;
    bool operator<(const node &dd)const{
        return w>dd.w;
    } //权值小的优先
};
vector<node>q[N];
bool vis[N];
//堆优化的prim算法
LL ans;
 
void queue_prim()
{
    //以节点1为起点进行扩展安全边 生成最小树
    priority_queue<node>que;
    while(!que.empty())
        que.pop(); //初始化清空优先队列 维护一个小根堆
                  //这样每次找安全边的速度就提高了
    ans = 0;
    memset(vis, false, sizeof(vis));
    for(int i=0; i<q[1].size(); i++){
        que.push(q[1][i]); //将起点的所有连接边全部加入队列中来
    }
    vis[1]=true;
    int edge=n-1;//边数
    node cur;
    while(edge--)
    {
        cur = que.top();
        que.pop();//这个地方需要注意一下
                  //并不是每个从优先队列取出来的边都是可以加到生成树上去的
 
        if(vis[cur.v]==true){
            while(vis[cur.v]){
                cur=que.top(); que.pop();
            }
        }
        ans = ans+cur.w; //printf("%d--  ", cur.w );
        vis[cur.v]=true; //加入生成树的该点将被标记访问
        for(int i=0; i<q[cur.v].size(); i++){
            if(vis[ q[cur.v][i].v ]==false) //当前加入生成树的点可以扩充出的边指向的节点
                que.push(q[cur.v][i]);//如果没有被访问才会加入到队列当中来
        }
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
    int i, j;
    int u, v, w;
    node cur;
    for(i=0; i<=n; i++)
        q[i].clear();
 
    for(i=0; i<m; i++)
    {
       scanf("%d %d %d", &u, &v, &w);
       cur.v=v; cur.w=w;
       q[u].push_back(cur);
       cur.v=u;
       q[v].push_back(cur); //建立双向边
    }
    queue_prim();
    printf("%lld
", ans );
    return 0;
}