# 743. 网络延迟时间 (Medium)

## 问题描述
[743. 网络延迟时间 (Medium)](https://leetcode.cn/problems/network-delay-time/)

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

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

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

**示例 1：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065444.png)

```
输入：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 的最短路长度，如果前者小于后者，就用前者更新后者。这种操作也被叫做「松弛」。

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

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

## 代码
```cpp
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;
    }
};
```