0743. Network Delay Time ======================================================================================================================== 题目信息 -------- :题号: 0743 :难度: Medium :主题: 有向图、传播时间、最短路径 :原题: `LeetCode 0743 `_ :重点: 节点编号从 ``1`` 到 ``n``,边有方向且权重为传播时间;返回从起点使所有节点首次收到信号所需的最短总时间,不可达时返回 ``-1`` 题目重述 -------- 给定由 ``n`` 个节点组成的有向网络,节点编号为 ``1`` 到 ``n``。数组 ``times`` 中每个三元组 ``[u, v, w]`` 表示一条从节点 ``u`` 指向节点 ``v`` 的有向边,信号沿该边传播需要 ``w`` 个时间单位。 信号在时间 ``0`` 从节点 ``k`` 发出,并可沿有向边继续传播。返回让所有节点都收到信号所需的最短时间;也就是各节点从 ``k`` 出发能够达到的最早接收时间中的最大值。若至少有一个节点无法从 ``k`` 到达,返回 ``-1``。 ``1 <= k <= n <= 100``,``1 <= times.length <= 6000``;每条边满足 ``1 <= u, v <= n``、``u != v``、``0 <= w <= 100``,并且同一有序节点对 ``(u, v)`` 不会出现多条边。 自建示例 -------- 间接路径比直接路径更快: .. code-block:: text 输入:times = [[1,2,4],[1,3,2],[3,2,1],[2,4,2],[3,4,7]], n = 4, k = 1 输出:5 解释:节点 3 在时间 2 收到信号;节点 2 经 1 -> 3 -> 2 在时间 3 收到;节点 4 再经节点 2 于时间 5 收到。所有节点最晚在时间 5 收到信号。 存在不可达节点: .. code-block:: text 输入:times = [[2,1,1]], n = 3, k = 2 输出:-1 解释:信号能从节点 2 到达节点 1,但无法到达节点 3,因此返回 -1。