0743. Network Delay Time¶
题目信息¶
- 题号:
0743
- 难度:
Medium
- 主题:
有向图、传播时间、最短路径
- 原题:
- 重点:
节点编号从
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) 不会出现多条边。
自建示例¶
间接路径比直接路径更快:
输入: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 收到信号。
存在不可达节点:
输入:times = [[2,1,1]], n = 3, k = 2
输出:-1
解释:信号能从节点 2 到达节点 1,但无法到达节点 3,因此返回 -1。