1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        vector<vector<int>> g(n, vector<int>(n, INT_MAX / 2));// 定义图， g[i][j] 
        for (auto& t : times) {
            g[t[0] - 1][t[1] - 1] = t[2];
        }
        vector<int> dis(n, INT_MAX / 2), done(n); // dis[i] 表示k-> i的最短路
        dis[k - 1] = 0; // 起始节点为k 起始距离为0
        while (true) {
            int x = -1;
            for (int i = 0; i < n; i++) { // 遍历dis 寻找距离最短的点
                if (!done[i] && (x < 0 || dis[i] < dis[x])) {
                    x = i; 
                }
            }
            // 如果 没有找到未处理的点，直接返回
            if (x < 0)
                return ranges::max(dis);
            // 如果找到的距离最小的点的距离还是inf 返回-1，表示不可达
            if (dis[x] == INT_MAX / 2)
                return -1;
            done[x] = true; // 更新该节点为访问过
            for (int y = 0; y < n; y++) {
                dis[y] = min(dis[y], dis[x] + g[x][y]); // 以当前节点为起始节点，更新最小距离
            }
        }
    }
};