到达目的地的第二短时间

标签: 广度优先搜索 图 最短路

难度: Hard

城市用一个 双向连通 图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边。每组节点对由 最多一条 边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 time 分钟。

每个节点都有一个交通信号灯，每 change 分钟改变一次，从绿色变成红色，再由红色变成绿色，循环往复。所有信号灯都 同时 改变。你可以在 任何时候 进入某个节点，但是 只能 在节点 信号灯是绿色时 才能离开。如果信号灯是  绿色 ，你 不能 在节点等待，必须离开。

第二小的值 是 严格大于 最小值的所有值中最小的值。

  • 例如，[2, 3, 4] 中第二小的值是 3 ，而 [2, 2, 4] 中第二小的值是 4 。

给你 n、edges、time 和 change ，返回从节点 1 到节点 n 需要的 第二短时间 。

注意：

  • 你可以 任意次 穿过任意顶点，包括 1 和 n 。
  • 你可以假设在 启程时 ，所有信号灯刚刚变成 绿色 。

示例 1：

       

输入：n = 5, edges = [[1,2],[1,3],[1,4],[3,4],[4,5]], time = 3, change = 5
输出：13
解释：
上面的左图展现了给出的城市交通图。
右图中的蓝色路径是最短时间路径。
花费的时间是：
- 从节点 1 开始，总花费时间=0
- 1 -> 4：3 分钟，总花费时间=3
- 4 -> 5：3 分钟，总花费时间=6
因此需要的最小时间是 6 分钟。

右图中的红色路径是第二短时间路径。
- 从节点 1 开始，总花费时间=0
- 1 -> 3：3 分钟，总花费时间=3
- 3 -> 4：3 分钟，总花费时间=6
- 在节点 4 等待 4 分钟，总花费时间=10
- 4 -> 5：3 分钟，总花费时间=13
因此第二短时间是 13 分钟。

示例 2：

输入：n = 2, edges = [[1,2]], time = 3, change = 2
输出：11
解释：
最短时间路径是 1 -> 2 ，总花费时间 = 3 分钟
第二短时间路径是 1 -> 2 -> 1 -> 2 ，总花费时间 = 11 分钟

提示：

  • 2 <= n <= 104
  • n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • 不含重复边
  • 每个节点都可以从其他节点直接或者间接到达
  • 1 <= time, change <= 103

Submission

运行时间: 238 ms

内存: 22.8 MB

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        G = [[] for _ in range(n+1)]
        for u,v in edges:
            G[u].append(v)
            G[v].append(u)
        vis = [-1] * (n+1)
        q = deque([(1, 0)])
        vis[1] = 0
        while q:
            i, t = q.popleft()
            if t % (2 * change) < change:
                t1 = t + time
            else:
                t1 = (t // change + 1) * change + time
            for j in G[i]:
                if t1 > vis[j]:
                    vis[j] = t1 if vis[j] == -1 else math.inf
                    q.append((j, t1))
                    if j == n and vis[j] == math.inf:
                        return t1

Explain

本题解采用广度优先搜索 (BFS) 算法来寻找从节点 1 到节点 n 的第二短路径时间。算法首先构建了一个邻接表 G 来表示图中的节点和边。然后，使用一个队列 q 来进行 BFS，其中队列中的每个元素是一个元组，包含当前节点编号和到达该节点的时间。时间 t1 根据当前时间和信号灯周期 change 计算，以决定是否需要等待红灯。如果当前时间 t 处于绿灯阶段，则直接加上通过时间 time；如果处于红灯阶段，则需等待至下一个绿灯开始，再加上通过时间。每遍历到一个新节点，如果该节点未被访问过，或者可以在更短的时间内到达，则更新到达时间并将其加入队列。算法的目标是找到第二短的到达时间，因此在到达节点 n 时，需要检查是否已有更短的路径存在，如果已经是第二次到达，则返回该时间作为结果。

时间复杂度: O(V + E)

空间复杂度: O(V + E)

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        # 创建邻接表
        G = [[] for _ in range(n+1)]
        for u, v in edges:
            G[u].append(v)
            G[v].append(u)
        # 初始化访问时间数组
        vis = [-1] * (n+1)
        q = deque([(1, 0)])
        # 初始节点1的访问时间
        vis[1] = 0
        while q:
            i, t = q.popleft()
            # 计算下一个信号灯是绿色的时间点
            if t % (2 * change) < change:
                t1 = t + time
            else:
                t1 = (t // change + 1) * change + time
            # 遍历当前节点所有邻接节点
            for j in G[i]:
                if t1 > vis[j]:
                    vis[j] = t1 if vis[j] == -1 else math.inf
                    q.append((j, t1))
                    # 如果到达终点，并且是第二次到达，返回时间
                    if j == n and vis[j] == math.inf:
                        return t1

Explore

在本题的算法设计中，通过设置访问时间数组 vis 来管理每个节点的访问状态，确保可以正确处理环和重复路径的情况。在第一次到达任何节点时，我们记录其到达时间。如果后续有其他路径再次到达该节点，而且到达时间晚于第一次，我们会继续考虑这个时间点，因为它可能代表着一个有效的第二短路径。这样即便图中存在环或节点被多次访问，算法也能正确地考虑这些路径对第二短路径的潜在贡献。

在这个特定的解法中，我们对传统的 BFS 进行了修改，允许节点在特定条件下被重新访问。具体地，我们使用 vis 数组记录到达每个节点的最短时间。当我们通过不同的路径到达同一个节点并且提供了一个更晚的到达时间时，我们会考虑这个新的到达时间，并将其加入队列中以供进一步的路径探索。这种方法允许我们捕捉到第二短路径，因为即使一个节点已被访问，只要有可能找到更长的路径（作为第二短路径的候选），我们就继续探索这个路径。