题解 | 最小生成树

#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int整型 n户人家的村庄
     * @param m int整型 m条路
     * @param cost int整型vector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int整型
     */
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        // write code here
        using pii = pair<int, int>;
        vector<vector<pii>> graph(n + 1);
        vector<bool> visited(n + 1, false);
        for (auto& v : cost) {
            graph[v[0]].push_back({v[2], v[1]});
            graph[v[1]].push_back({v[2], v[0]});
        }

        priority_queue<pii, vector<pii>, greater<pii>> prq;
        prq.push({0, 1});
        int cnt = 0;
        int sum = 0;
        while (!prq.empty() && cnt < n) {
            int u = prq.top().second;
            int w = prq.top().first;
            prq.pop();
            if (visited[u]) {
                continue;
            }
            sum += w;
            visited[u] = true;
            cnt++;
            for (auto& p : graph[u]) {
                cout << p.second << "," << p.first << endl;
                if (!visited[p.second]) {
                    prq.push(p);
                }
            }
        }

        return cnt == n ? sum : 0;
    }
};