743. 网络延迟时间 (Medium)

标签：vector 743 idx pq times 延迟时间 Medium 节点 dis

问题描述

743. 网络延迟时间 (Medium)

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

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

现在，从某个节点 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

提示：

• 1 <= k <= n <= 100
• 1 <= times.length <= 6000
• times[i].length == 3
• 1 <= uᵢ, vᵢ <= n
• uᵢ != vᵢ
• 0 <= wᵢ <= 100
• 所有 (uᵢ, vᵢ) 对都 互不相同（即，不含重复边）

解题思路

Dijkstra算法，堆优化。

使用一个三维数组vector<vector<vector<int>>> dp，dp[i]存储了与点i相连的点及其权值；

将所有节点分成两类：已确定从起点到当前点的最短路长度的节点，以及未确定从起点到当前点的最短路长度的节点（下面简称「未确定节点」和「已确定节点」）。

每次从「未确定节点」中取一个与起点距离最短的点，将它归类为「已确定节点」，并用它「更新」从起点到其他所有「未确定节点」的距离。直到所有点都被归类为「已确定节点」。

用节点 AAA「更新」节点 BBB 的意思是，用起点到节点 AAA 的最短路长度加上从节点 AAA 到节点 BBB 的边的长度，去比较起点到节点 BBB 的最短路长度，如果前者小于后者，就用前者更新后者。这种操作也被叫做「松弛」。

这里暗含的信息是：每次选择「未确定节点」时，起点到它的最短路径的长度可以被确定。

我们利用一个优先队列（小顶堆）来维护该过程。

代码

class Solution {
  public:
    int networkDelayTime(vector<vector<int>> &times, int n, int k) {
        vector<vector<vector<int>>> graph(n + 1);
        for (auto &vec : times) {
            graph[vec[0]].push_back({vec[1], vec[2]}); // vec1表示目标节点,vec[2]表示距离
        }
        // Dijkstra算法
        vector<int> dis(n + 1, -1);    // 表示从k到各点的最短距离, -1表示这个点还没有到达
        vector<int> min_dis(n + 1, 0); //为0表示还没找到该该点的最短距离
        auto cmp = [&](pair<int, int> &p1, pair<int, int> &p2) {
            return p1.second > p2.second;
        };
        // 小顶堆，pair.first为点坐标，pair.second为时间
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
        pq.push({k, 0});
        dis[k] = 0;
        while (!pq.empty()) {
            auto [idx, len] = pq.top();
            pq.pop();
            if (min_dis[idx] == 1) // 如果已经找到最短距离，直接进行下一次循环
                continue;
            dis[idx] = len; // 用最短距离更新dis[idx]
            min_dis[idx] = 1; // 说明该点已经找到最短距离
            for (auto &v : graph[idx]) {
                if (min_dis[v[0]] == 0) {
                    pq.push({v[0], len + v[1]});
                }
            }
        }
        int res = 0;
        for (int i = 1; i <= n; ++i) {
            if (min_dis[i] == 0) {
                return -1;
            }
            res = std::max(res, dis[i]);
        }
        return res;
    }
};

标签：vector,743,idx,pq,times,延迟时间,Medium,节点,dis
From： https://www.cnblogs.com/zwyyy456/p/17208183.html