题解 | #最小生成树#

class Solution {
public:
    const int inf = 0x3f3f3f3f;
    struct Node{
        int v;
        int c;
        Node(int _v, int _c):v(_v), c(_c){}
        bool operator < (const Node& other) const{
            return c > other.c;
        }
    };
    int Adj[5010][5010];
    int vis[5010];
    int dist[5010];
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        memset(Adj, inf, sizeof(Adj));
        memset(vis, false, sizeof(vis));
        memset(dist, inf, sizeof(dist));
        for(int i = 0 ; i < m; i ++){
            int u = cost[i][0] - 1;
            int v = cost[i][1] - 1;
            int c = cost[i][2];
            //去重边
            Adj[u][v] = min(Adj[u][v], c);
            Adj[v][u] = min(Adj[v][u], c);
        }
        priority_queue<Node> pq;
        pq.push({0, 0});
        dist[0] = 0;
        int ans = 0;
        int cnt = 0; //已经加入生成树集合的村庄数
        while(!pq.empty()){
            Node node = pq.top(); pq.pop();
            int u = node.v, cos = node.c;
            if(!vis[u]){
                ans += cos;
                vis[u] = true;
                cnt ++;
                if(cnt == n) break;
            }else continue;
            for(int v = 0; v < n; v ++){
                if(Adj[u][v] == inf) continue;
                int c = Adj[u][v];
                if(!vis[v] && c < dist[v]){
                    pq.push({v, c});
                    dist[v] = c;
                }
            }
        }
        return ans;
    }
};