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

示例 2：

输入：n = 2, edges = [[1,2]], time = 3, change = 2
输出：11

约束条件：

  • 2 <= n <= 10^4
  • n - 1 <= edges.length <= min(2 * 10^4, n * (n - 1) / 2)
  • edges[i].length == 2
  • 1 <= ui, vi <= n
  • ui != vi
  • 没有重复的边
  • 每个顶点都可以直接或间接到达其他任何顶点
  • 1 <= time, change <= 10^3

解题思路

这道题需要找到从节点1到节点n的第二短路径。由于涉及信号灯的约束，我们不能简单地使用传统的最短路算法。

核心思路：

  1. 建图阶段：构建邻接表表示图结构。

  2. BFS搜索：使用广度优先搜索找到所有可能的路径时间。关键在于对每个节点，我们需要记录到达该节点的最短时间和第二短时间。

  3. 信号灯处理：

    • 每当到达一个节点时，需要检查当前时间的信号灯状态
    • 如果是红灯，需要等待到下一个绿灯周期
    • 时间为 t 时，如果 (t // change) % 2 == 1，则为红灯

  4. 状态记录：为每个节点维护两个时间：

    • dist1[i]：到达节点 i 的最短时间
    • dist2[i]：到达节点 i 的第二短时间

  5. 剪枝优化：如果当前时间已经大于等于已知的第二短时间，可以剪枝。

算法流程：

  • 从节点1开始BFS
  • 对于每个节点，尝试更新其邻居的最短和第二短时间
  • 当找到到达节点n的第二短时间时返回结果

代码实现

class Solution {
public:
    int secondMinimum(int n, vector<vector<int>>& edges, int time, int change) {
        vector<vector<int>> graph(n + 1);
        for (auto& edge : edges) {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        
        vector<int> dist1(n + 1, -1), dist2(n + 1, -1);
        queue<pair<int, int>> q; // {node, time}
        q.push({1, 0});
        dist1[1] = 0;
        
        while (!q.empty()) {
            auto [node, curTime] = q.front();
            q.pop();
            
            // Calculate actual departure time considering traffic light
            int departTime = curTime;
            if ((departTime / change) % 2 == 1) {
                departTime = (departTime / change + 1) * change;
            }
            
            for (int neighbor : graph[node]) {
                int arrivalTime = departTime + time;
                
                if (dist1[neighbor] == -1) {
                    dist1[neighbor] = arrivalTime;
                    q.push({neighbor, arrivalTime});
                } else if (dist2[neighbor] == -1 && arrivalTime > dist1[neighbor]) {
                    dist2[neighbor] = arrivalTime;
                    q.push({neighbor, arrivalTime});
                }
            }
        }
        
        return dist2[n];
    }
};

class Solution:
    def secondMinimum(self, n: int, edges: List[List[int]], time: int, change: int) -> int:
        from collections import defaultdict, deque
        
        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)
        
        dist1 = [-1] * (n + 1)
        dist2 = [-1] * (n + 1)
        q = deque([(1, 0)])  # (node, time)
        dist1[1] = 0
        
        while q:
            node, cur_time = q.popleft()
            
            # Calculate actual departure time considering traffic light
            depart_time = cur_time
            if (depart_time // change) % 2 == 1:
                depart_time = (depart_time // change + 1) * change
            
            for neighbor in graph[node]:
                arrival_time = depart_time + time
                
                if dist1[neighbor] == -1:
                    dist1[neighbor] = arrival_time
                    q.append((neighbor, arrival_time))
                elif dist2[neighbor] == -1 and arrival_time > dist1[neighbor]:
                    dist2[neighbor] = arrival_time
                    q.append((neighbor, arrival_time))
        
        return dist2[n]

public class Solution {
    public int SecondMinimum(int n, int[][] edges, int time, int change) {
        var graph = new List<int>[n + 1];
        for (int i = 0; i <= n; i++) {
            graph[i] = new List<int>();
        }
        
        foreach (var edge in edges) {
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        
        var dist1 = new int[n + 1];
        var dist2 = new int[n + 1];
        Array.Fill(dist1, -1);
        Array.Fill(dist2, -1);
        
        var queue = new Queue<(int node, int time)>();
        queue.Enqueue((1, 0));
        dist1[1] = 0;
        
        while (queue.Count > 0) {
            var (node, curTime) = queue.Dequeue();
            
            // Calculate actual departure time considering traffic light
            int departTime = curTime;
            if ((departTime / change) % 2 == 1) {
                departTime = (departTime / change + 1) * change;
            }
            
            foreach (int neighbor in graph[node]) {
                int arrivalTime = departTime + time;
                
                if (dist1[neighbor] == -1) {
                    dist1[neighbor] = arrivalTime;
                    queue.Enqueue((neighbor, arrivalTime));
                } else if (dist2[neighbor] == -1 && arrivalTime > dist1[neighbor]) {
                    dist2[neighbor] = arrivalTime;
                    queue.Enqueue((neighbor, arrivalTime));
                }
            }
        }
        
        return dist2[n];
    }
}

var secondMinimum = function(n, edges, time, change) {
    const graph = Array.from({length: n + 1}, () => []);
    for (const [u, v] of edges) {
        graph[u].push(v);
        graph[v].push(u);
    }
    
    const dist = Array.from({length: n + 1}, () => [-1, -1]);
    const queue = [[1, 0]];
    dist[1][0] = 0;
    
    while (queue.length > 0) {
        const [node, currTime] = queue.shift();
        
        for (const neighbor of graph[node]) {
            let newTime = currTime;
            
            const cycle = Math.floor(newTime / change);
            if (cycle % 2 === 1) {
                newTime = (cycle + 1) * change;
            }
            newTime += time;
            
            if (dist[neighbor][0] === -1) {
                dist[neighbor][0] = newTime;
                queue.push([neighbor, newTime]);
            } else if (dist[neighbor][1] === -1 && dist[neighbor][0] !== newTime) {
                dist[neighbor][1] = newTime;
                queue.push([neighbor, newTime]);
            }
        }
    }
    
    return dist[n][1];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(V + E)V为顶点数，E为边数。每个节点最多被访问两次（最短路径和第二短路径各一次）
空间复杂度O(V + E)图的邻接表存储和BFS队列的空间开销

相关题目