算法：网络延迟时间

题目：
有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1
示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/network-delay-time

思路：
信号的速度是固定的，需要的时间和距离是成正比的。需要多久就是需要多远。而本题从点A到点B，需要走过的距离就是点A到点B的最短距离。而本题答案就是从源点K到其他各个点的最短距离中的最大值。单源最短路径算法Dijkstra刚好合适。

代码：

int networkDelayTime(vector<vector<int>>& times, int n, int k) {
    const int inf = INT_MAX/2;
    vector<vector<int>> e(n+1,vector<int>(n+1,inf));
    vector<int> dis(n+1,inf);
    vector<int> book(n+1,0);
    dis[k] = 0;
    for(int i = 0;i < times.size();i++) {
        e[times[i][0]][times[i][1]] = times[i][2];
        if(times[i][0] == k) {
            dis[times[i][1]] = times[i][2];
        }
    }
    
    for(int i = 1;i < n;i++) {
        //找最小值
        int min = inf;
        int u = -1;
        for(int j = 1;j < n+1;j++) {
            if (book[j] == 0 && dis[j] < min) {
                min = dis[j];
                u = j;
            }
        }
        if (u == -1) {
            //没找到
            continue;
        }
        book[u] = 1;
        for(int v = 1;v < n+1;v++) {
            if (e[u][v] < inf) {
                if(dis[v] > dis[u] + e[u][v]) {
                    dis[v] = dis[u] + e[u][v];
                }
            }
        }
    }
    int ans = -1;
    for(int i = 1;i < n+1;i++) {
        if (dis[i] > ans) {
            ans = dis[i];
        }
    }
    if (ans == inf) {
        return -1;
    }
    return ans;
}