743 网络延迟时间

2022 年 3 月 21 日
本文字数：734 字
阅读完需：约 2 分钟

题意：网络中有 n 个节点，以及各节点到邻接节点的延迟，从第 k 个节点出发，问需要多少时间，最少需要多少时间才能到达所有节点。

分析：最长时间就是 k 到 1..n 的所有节点的最大值。有几种方式可以实现，比如 BFS 的 SPFA，基于贪心的 dijkstra 算法，基于动态规划的贝尔曼福特算法（输出 dist 和 predecessor），本次实现使用 dijkstra 算法（输出 dist 和 used）找。

步骤：

初始化二维数组的邻接表，从 src 到 dst，需要多少 cost。构建 dist，used 一维数组，初始化为 inf 和 false。注意 inf 需要是 INT_MAX/2。核心步骤是松弛节点。分为两步，第一个步骤是 x 为-1，或者有更短的路径时，更新为新值。第二个步骤是使用邻接表更新 dist 的值。得到结果就是找 dist 里的最大值即可。如果最大值有个 inf，也就是不可达的，返回-1。

class Solution {public:    int networkDelayTime(vector<vector<int>>& times, int n, int k) {        const int inf = INT_MAX / 2;        vector<vector<int>> g(n, vector<int>(n, inf));        for (auto time : times) {            g[time[0] -  1][time[1] - 1] = time[2];        }
        vector<int> dist(n, inf);        vector<bool> used(n, false);        dist[k - 1] = 0;
        for (int i = 0; i < n; i++) {            int x = -1;            for (int y = 0; y < n; y++) {                if (!used[y] && (x == -1 || dist[y] < dist[x])) x = y;            }            used[x] = true;            for (int y = 0; y < n; y++) {                dist[y] = min(dist[y], dist[x] + g[x][y]);            }        }
        int ans = *max_element(dist.begin(), dist.end());        return ans == inf ? -1 : ans;    }};

复制代码

发布于: 刚刚阅读数: 2

好吃不贵

关注

还未添加个人签名 2018.11.20 加入

还未添加个人简介

发布

暂无评论

创作场景

743 网络延迟时间

好吃不贵

评论