【算法入门&图论】【模板】拓扑排序|【模板】单源最短路2 |最小生成树（下）

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 返回最小的花费代价使得这n户人家连接起来
     * @param n int n户人家的村庄
     * @param m int m条路
     * @param cost intvector<vector<>> 一维3个参数，表示连接1个村庄到另外1个村庄的花费的代价
     * @return int
     */
    // 自定义排序规则：按权递增
    static bool cmp(vector<int>& x, vector<int>& y) {
        return x[2] < y[2];
    }
    int miniSpanningTree(int n, int m, vector<vector<int> >& cost) {
        unordered_set<int> points; // 记录不重复的点
        int res = 0;
        sort(cost.begin(), cost.end(), cmp);
        res += cost[0][2]; // 此时res 为最小权值
        // 将最小边加入
        points.insert(cost[0][0]);
        points.insert(cost[0][1]);
        while (1) {
            if (points.size() == n)
                break; // 所有的点连同后退出循环
            // 遍历剩余的边
            for (auto it = cost.begin(); it != cost.end(); it++) {
                // 如果边仅有一个点在集合内就加入
                if ((points.find((*it)[0]) != points.end() &&
                    points.find((*it)[1]) == points.end()) ||
                    (points.find((*it)[1]) != points.end() &&
                    points.find((*it)[0]) == points.end()))
                    {
                        res += (*it)[2];
                        points.insert((*it)[0]);
                        points.insert((*it)[1]);
                        cost.erase(it); // 删除该边
                        break;
                    }
            }
        }
        return res;
    }
};

#include<iostream>
#include<climits> // 使用INT_MAX所需要引入的头文件
using namespace std;
const int N = 5000; // 注意题干，图的点数是固定值5000
int main() {
    int G[N + 1][N + 1]; // 用于模拟邻接矩阵进行建图
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            G[i][j] = INT_MAX; // 先将邻接矩阵全部初始化为无穷大
        }
    }
    int n, m;
    cin >> n >> m;
    int u, v, w;
    for (int i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        G[u][v] = w;
        G[v][u] = w; // 需要关于主对角线对称，因此两边都需要存储
    }
    int dist[N + 1]; // 用于存储每个顶点当前与源点的最短距离
    bool flag[N + 1]; // 用于记录每个顶点是否已经完成与源点最短距离的计算处理
    for (int i = 1; i <= N; i++) {
        dist[i] = G[1][i]; // 初始设置为邻接矩阵中源点所在 行 的权值
        flag[i] = false;
    }
    dist[1] = 0;
    flag[1] = true; // 将源点加入已处理集合
    for (int i = 2; i <= N; i++) {
        int tmp = INT_MAX, index = 1;
        for (int j = 1; j <= N; j++) { // 遍历寻找与源点的最短距离
            if (flag[j] == false && dist[j] < tmp) {
                tmp = dist[j];
                index = j;
            }
        }
        if (index != 1) {
            flag[index] = true; // 找到后将其加入已处理集合
        }
        for (int j = 2; j <= N; j++) {
            if (flag[j] == false && G[index][j] != INT_MAX) {
                if (G[index][j] + dist[index] < dist[j]) {
                    dist[j] = G[index][j] + dist[index]; // 更新最短路径
                }
            }
        }
    }
    if (dist[n] != INT_MAX) {
        cout << dist[n];
    } else {
        cout << -1;
    }
    return 0;
}