4122. 信号激活的最早时刻
难度中等
题目描述
给你一个整数 n 和一张包含 n 个节点的 有向 图,节点编号从 0 到 n - 1。该图用二维数组 edges 表示,其中 edges[i] = [ui, vi, delayi] 表示一条从节点 ui 指向节点 vi 的边,信号沿这条边传播需要 delayi 个时间单位。
如果存在一条从节点 u 指向节点 v 的边,则称节点 u 是节点 v 的一个 入邻居。
节点 0 在时刻 0 处于 激活 状态,其余节点初始时均未激活。
当一个节点在时刻 t 激活时,它会 立即 沿每条 出边 各发送一个信号。节点一旦激活,就会保持激活状态,不会再次发送这些信号。沿一条延迟为 d 的边发送的信号会在时刻 t + d 到达。
另给你一个长度为 n 的整数数组 requiredSignals,其中 requiredSignals[i] 表示节点 i 在激活之前 必须 从多少个 不同的入邻居 收到信号。
对于尚未激活的节点 i,它会在收到来自 至少 requiredSignals[i] 个 不同的入邻居 的信号的 最早 时刻 t 激活。
返回一个长度为 n 的数组 ans,其中 ans[i] 是节点 i 激活的 最早 时刻。如果节点 i 永远不会 激活,则 ans[i] 应为 -1。
注意: requiredSignals[0] 的值不影响结果,因为节点 0 在时刻 0 就已激活,并在该时刻沿出边发送信号。
示例 1:
输入: n = 3, edges = [[0,1,1],[0,2,1]], requiredSignals = [1,1,2]
输出: [0,1,-1]
解释:
- 节点 0 在时刻 0 处于激活状态,向节点 1 和节点 2 发送信号。
- 在时刻 1,两个信号均已到达。节点 1 收到了所需的 1 个信号,因此激活。
- 节点 2 需要收到来自 2 个不同入邻居的信号,但它只有一个入邻居,因此永远不会激活。
- 因此,
ans = [0, 1, -1]。
示例 2:
输入: n = 4, edges = [[0,1,1],[0,2,1],[1,3,2],[2,3,2]], requiredSignals = [3,1,1,2]
输出: [0,1,1,3]
解释:
- 尽管
requiredSignals[0] = 3,节点 0 在时刻 0 仍处于激活状态,并向节点 1 和节点 2 发送信号。 - 在时刻 1,节点 1 和节点 2 各自收到所需的 1 个信号并激活,随后各自立即向节点 3 发送一个信号。
- 两个信号都在时刻
1 + 2 = 3到达节点 3。它们来自两个不同的入邻居,因此节点 3 在时刻 3 激活。 - 因此,
ans = [0, 1, 1, 3]。
示例 3:
输入: n = 4, edges = [[0,1,2],[1,2,3],[0,2,5],[2,3,1]], requiredSignals = [3,1,2,1]
输出: [0,2,5,6]
解释:
- 节点 0 在时刻 0 处于激活状态,向节点 1 和节点 2 发送信号。
- 节点 1 在时刻 2 收到信号,随即激活并向节点 2 发送一个信号。
- 在时刻 5,节点 2 收到来自节点 0 和节点 1 的信号,其中来自节点 1 的信号到达时刻为
2 + 3 = 5。节点 2 已收到来自 2 个不同入邻居的信号,满足激活条件,于是激活并向节点 3 发送一个信号。 - 节点 3 在时刻
5 + 1 = 6收到该信号并激活。 - 因此,
ans = [0, 2, 5, 6]。
示例 4:
输入: n = 4, edges = [[0,1,2],[1,0,1],[1,2,1],[2,3,1],[3,2,1]], requiredSignals = [3,1,2,1]
输出: [0,2,-1,-1]
解释:
- 节点 0 在时刻 0 处于激活状态,向节点 1 发送一个信号。
- 节点 1 在时刻 2 激活,并向节点 0 和节点 2 发送信号。这两个信号都在时刻 3 到达。
- 节点 0 已经激活,因此收到另一个信号后不会再次发送信号。
- 节点 2 必须收到节点 1 和节点 3 各自发出的信号,但它只收到了节点 1 发出的信号。节点 3 正在等待来自节点 2 的信号,因此节点 2 和节点 3 都不会激活。
- 因此,
ans = [0, 2, -1, -1]。
提示:
2 <= n == requiredSignals.length <= 1050 <= edges.length <= 105edges[i] = [ui, vi, delayi]0 <= ui, vi <= n - 1ui != vi1 <= delayi <= 109- 从任意节点
ui到任意节点vi至多有一条有向边。 1 <= requiredSignals[i] <= n - 1
解法
方法一
1 | |
1 | |
1 | |
1 | |