题意整理：

去除题目背景后,实际上就是需要对一个给定边权的图,求其最小生成树.
最小生成树:在一个具有N个顶点的带权连通图G中，如果存在某个子图G'，其包含了图G中的所有顶点和一部分边，且不形成回路，并且子图G'的各边权值之和最小，则称G'为图G的最小生成树。注意到最小生成树并不唯一
最小生成树有两种常用的算法,既Kruskal算法和Prim算法

方法一：Kruskal算法

核心思想：

Kruskal算法的核心思想是：在带权连通图中，不断地在边集合中找到最小的边，如果该边满足得到最小生成树的条件，就将其加入，直到得到一颗最小生成树。
具体的执行步骤：
1：在带权连通图中，将边按权值排序,从权值最小的边开始执行2
2：判断是否能够选择这条边,依据是边的两个顶点是否已连通，如果不连通就选择这条边使其连通。
3：循环2，直到图中所有的顶点都在同一个连通分量中，即得到最小生成树。在这里,如果所有点在一个连通分量中,被选择的边数必为n - 1,故可以简单判断选择的边数判断
最小生成树采用并查集实现
对于下面的图,步骤为:

1.对边(1,3)，符合条件，选择该边，此时集合为{1,3},{2},{4},{5}
2.对边(1,4)，符合条件，选择该边，此时集合为{1,3,4},{2},{5}
3.对边(3,4)，不符合条件，不选择该边
4.对边(1,2)，符合条件，选择该边，此时集合为{1,2,3,4},{5}
5.对边(2,4)，不符合条件，不选择该边
6.对边(2,5)，符合条件，选择该边，此时集合为{1,2,3,4,5},全部点在同一个连通分量中，循环结束

核心代码：

class Solution {
public:
    int father[50001]; //节点的父节点

    void init(int n) {
        for (int i = 0; i < n; i++) {  // 初始化父节点为自身
            father[i] = i;
        }
    }

    int find(int x) { 
        // 路径压缩和寻根
        return x == father[x] ? x : father[x] = find(father[x]); 
    }

    void join(int x, int y) { //合并节点
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            father[rootX] = rootY;
        }
    }

    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        //按边权对边排序
        sort(cost.begin(), cost.end(), [&](vector<int>& a, vector<int>& b) {
            return a[2] < b[2];
        });
        int p = n - 1;//所需边数
        int ans = 0;
        init(n);
        for(vector<int>& it : cost) {
            if(find(it[0]) != find(it[1])) {
                //不在一个连通分量中,合并
                join(it[0], it[1]);
                ans += it[2];
                if(--p == 0) {
                    //边数足够,不再循环
                    break;
                } 
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：。对边的排序复杂度为,合并操作对每个节点操作一次,复杂度为,故总的时间复杂度为
空间复杂度：,既并查集消耗空间

方法二：Prim算法

核心思想：

Prim算法的步骤是：初始化已加入集合U,图中点集为V,在带权连通图中，从图中某一顶点v开始，此时集合U={v}，重复执行下述操作：在所有u∈U,w∈V-U的边(u,w)∈E中找到一条权值最小的边，将(u,w)这条边加入到已找到边的集合，并且将点w加入到集合U中，当U=V时，就找到了这颗最小生成树。

1.选择点1作为起始，加入可选择边(1,3),(1,4),(1,2),U={1}
2.选择点3，此时可选边为(1,4),(1,2),(3,4),U={1,3}
3.选择点4，此时可选边为(1,2),(4,2),(4,5),U={1,3,4}
4.选择点2，此时可选边为(4,5),(2,5),U={1,2,3,4}
5.选择点5，U={1,2,3,4,5}，循环结束

核心代码：

class Solution {
public:
    struct cmp {
        //用于按距离排序
        bool operator()(pair<int, int> a, pair<int, int> b) {
            return a.first > b.first;
        }
    };
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        vector<vector<int>> dist(n, vector<int>(n, 100000));//邻接矩阵
        for(vector<int>& it : cost) {
            //将边加入,处理重边
            dist[it[0] - 1][it[1] - 1] = min(dist[it[0] - 1][it[1] - 1], it[2]);
            dist[it[1] - 1][it[0] - 1] = min(dist[it[1] - 1][it[0] - 1], it[2]);
        }
        int ans = 0, need = n;
        vector<int> vis(n);//判断是否访问过
        priority_queue<pair<int,int>, vector<pair<int, int>>, cmp> q;
        q.push({0, 0});//加入0节点
        while(need) {
            int c = q.top().first;
            int p = q.top().second;
            q.pop();
            //若节点未加入，加入并更新
            if(vis[p] == 0) {
                vis[p] = 1;
                ans += c;
                --need;
                for(int i = 0; i < n; ++i) {
                    if(!vis[i] && dist[p][i] < 100000) {
                        q.push({dist[p][i], i});
                    }
                }
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度：，需要选取n个点，每个点进行对其他n-1个点进行判断和加入，总的时间复杂度为
空间复杂度：,使用了大小为的邻接矩阵,队列和vis数组大小都为