[保姆级讲解+注释]面向新手蒟蒻的最小生成树prim算法代码实现

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e3+5;
const int MAXM = 2e5+10;
const int INF = 0x3f3f3f3f;

vector < pair<int,int> > g[MAXN]; //邻接表存图,这里的pair<int,int> 是一个二元组 分别存目标节点编号和两个节点的距离（权值）
int dist[MAXN];
bool vis[MAXN];


int main(){
    int n,m; //N 个结点和 M 条无向边
    cin >> n >> m;
    
    for (int i = 1; i <= m; i++){
        int u,v,w; // u,v节点存在一条距离（权值）为w的边
        cin >> u >> v >> w;
        g[u].push_back({v,w}); //存储
        g[v].push_back({u,w});
    }

    fill(vis + 1,vis + n + 1,false); //初始化vis记录所有节点都未访问
    fill(dist + 1,dist + n + 1,INF); //初始化dist使得所有节点与最小生成树的距离为一个极大值（因为此时还没有创建最小生成树，也就没有距离一说，赋值为极大值是为了方便后面在第一次更新距离的时候方便比较）

    priority_queue <pair<int,int> , vector<pair<int,int> >,greater<pair<int,int> > > pq; //优先队列用来获得当前与最小生成树距离最小的节点

    dist[1] = 0; //从任意节点开始皆可，这里从1号节点开始
    pq.push({0,1}); //将1号节点放入优先队列。距离为0（此时最小生成树只有一个1号节点），编号为1

    int tw = 0; //总距离（权值）
    int cnt = 0;//最小生成树的总节点数

    while(!pq.empty() && cnt < n){ //优先队列不为空且最小生成树总节点树小于整张图的总节点数

        int tmp_w = pq.top().first; //将到最小生成树距离最小的节点到最小生成树的距离（权值）赋值给tmp_w
        int tmp_u = pq.top().second; //将到最小生成树距离最小的节点的编号赋值给tmp_u
        pq.pop(); //移除已经加入最小生成树的节点
        
        if(vis[tmp_u]){ //如果该节点已经在最小生成树中直接跳过，因为同一个节点可能被多次加入优先队列（当发现更短距离时,也就是节点与最小生成树的距离更新的时候）,
            continue;
        }

        tw += tmp_w; //累加上该最小生成树节点的距离（权值）
        cnt++; //最小生成树节点+1

        vis[tmp_u] = true; //标记为已加入最小生成树

        for(const auto& edge : g[tmp_u]){ //遍历当前节点的所有邻居
            int u = edge.first; //获取这个邻居的编号
            int w = edge.second;//获取这个邻居与当前节点的距离；
            
            if(!vis[u] && w < dist[u]){ //当这个邻居节点没有被加入最小生成树且这个邻居节点与当前节点的距离（权值）比它之前与最小生成树的距离小时
                dist[u] = w; //这里因为当前节点已经加入最小生成树了，属于最小生成树的一部分，最小生成树更新了，那么节点与最小生成树的距离（dist[y])也要更新。也就是如果这个邻居节点与当前节点（当前节点是最小生成树的一部分）的距离比 dist[u] 中记录的值小的时候，更新节点u与最小生成树的距离
                pq.push({w,u}); //将节点与最小生成树的距离和编号放入优先队列（这里如果 dist[u] 更新过了，那么优先队列中会有两个编号一样的节点，但是因为是小根堆所以只会处理距离（权值）小的那一个
            }
        }
        
    }

    if(cnt < n){ //加入最小生成树的顶点数量比总顶点数小时
        cout << "orz" << '\n'; //输出不连通
    }

    else{
        cout << tw << '\n'; //输出总距离（权值）
    }


    return 0;
}