leetcode743. 网络延迟时间 DJ-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode743. 网络延迟时间 DJ。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

https://leetcode.cn/problems/network-delay-time/
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过有向边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

leetcode743. 网络延迟时间 DJ,笔记,算法文章来源地址https://www.toymoban.com/news/detail-599765.html

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {

    }
};

提示：
1 <= k <= n <= 100
1 <= times.length <= 6000
times[i].length == 3
1 <= ui, vi <= n
ui != vi
0 <= wi <= 100
所有 (ui, vi) 对都 互不相同（即，不含重复边）

code

可以建图，然后使用DJ

邻接矩阵

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 &t : times) {
            int x = t[0] - 1, y = t[1] - 1;//节点编号减小了 1，从而使节点编号位于 [0,n−1] 范围
            g[x][y] = t[2];//邻接矩阵图
        }

        vector<int> dist(n, inf);
        dist[k - 1] = 0;
        vector<int> used(n);
        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;
            //加入x后，更新最短距离的数组
            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;
    }
};

邻接链表

class dijkstra {
private:
    // nodes[v] = [{w1, d1}, {w2, d2}, {w3, d3}...]
    vector<vector<pair<int, int>>> nodes;
    // the number of nodes
    int n;
public:
    // init
    // nodes: edges[i][0]->edges[i][1]
    // distance: edges[i][2]
    dijkstra (int n, vector<vector<int>>& edges) {
        this->n = n;
        nodes.resize(n);
        // undirected graph
        for (auto& i : edges) {
            int node1 = i[0] - 1, node2 = i[1] - 1, d = i[2];
            nodes[node1].emplace_back(node2, d);
        }
    }

    // v0: source node
    vector<int> solve (int v0) {
        // pq.top() -> {d, v}: current minimum distance from v0
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;//https://www.bilibili.com/video/BV1s44y1H7ZM/?
        vector<int> dis(n, INT_MAX);
        dis[v0] = 0;
        pq.emplace(0, v0);
        vector<bool> vis(n, false);
        while (!pq.empty()) {
            pair<int, int> x = pq.top(); pq.pop();
            int d = x.first, w = x.second;

            if (vis[w]) continue;
            vis[w] = true;
            // dis[w] = d;
            for (auto& i : nodes[w]) {
                if (d + i.second < dis[i.first]) {
                    dis[i.first] = d + i.second;
                    pq.emplace(dis[i.first], i.first);
                }
            }
        }
        return dis;
    }
};

class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        dijkstra dj(n, times);
        vector<int> ans = dj.solve(k - 1);
        int ret = *max_element(ans.begin(), ans.end());
        return ret == INT_MAX ? -1 : ret;
    }
};