千问 LettCode 2045.到达目的地的第二短时间 public int secondMinimum(int n, int[][] edges, int time, int change)
import java.util.*;
public int secondMinimum(int n, int[][] edges, int time, int change) {
// 建图
List<Integer>[] graph = new List[n + 1];
for (int i = 1; i <= n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] e : edges) {
graph[e[0]].add(e[1]);
graph[e[1]].add(e[0]);
}
// dist[i][0] 最短, dist[i][1] 次短
int[][] dist = new int[n + 1][2];
for (int i = 1; i <= n; i++) {
Arrays.fill(dist[i], Integer.MAX_VALUE);
}
dist[1][0] = 0;
Queue<int[]> q = new LinkedList<>(); // [node, distance]
q.offer(new int[]{1, 0});
while (!q.isEmpty()) {
int[] cur = q.poll();
int u = cur[0], d = cur[1];
if (d > dist[u][1]) continue; // 已有更好的两个值
for (int v : graph[u]) {
int nd = d + 1;
if (nd < dist[v][0]) {
dist[v][1] = dist[v][0];
dist[v][0] = nd;
q.offer(new int[]{v, nd});
} else if (nd > dist[v][0] && nd < dist[v][1]) {
dist[v][1] = nd;
q.offer(new int[]{v, nd});
}
}
}
int secondShortest = dist[n][1]; // 第二短路径长度
// 模拟计算时间
long total = 0;
for (int i = 0; i < secondShortest; i++) {
if ((total / change) % 2 == 1) {
total = ((total / change) + 1) * change;
}
total += time;
}
return (int) total;
}
LeetCode 2045. 到达目的地的第二短时间 是一道结合图论（最短路径）与时间模拟的中等偏难题。我们需要找到从节点 1 到节点 n 的第二短的到达时间，其中每条边的通行时间受红绿灯周期 change 影响。
🧠 题意简析
- 图是无向图，节点编号从 1 到 n。
- 每次走一条边耗时 time 秒。
- 红绿灯规则：
- 起始时刻为 0。
- 每隔 change 秒切换一次：[0, change) 绿灯，[change, 2change) 红灯，[2change, 3*change) 绿灯，依此类推。
- 如果你到达某个节点的时刻落在红灯区间（即 (当前时间 // change) % 2 == 1），则必须等到下一个绿灯开始（即 (当前时间 // change + 1) * change）才能出发。
- 目标：求从节点 1 到节点 n 的第二短的总耗时（不是第二短路径长度，而是考虑红绿灯后的实际时间）。
注意：第二短时间 ≠ 第二短路径长度。但通常第二短时间对应的是第二短的路径长度（因为时间是路径长度的单调函数，虽然有等待，但路径越长，时间不会更短）。
✅ 解题思路
关键观察：
- 实际通行时间只依赖于路径的边数（即步数）。
- 因此，我们可以先求出从 1 到 n 的最短路径长度 d1 和 第二短路径长度 d2（要求 d2 > d1）。
- 然后根据 d2 计算出对应的实际时间（考虑红绿灯等待）。
所以分两步：
1. BFS 求最短和次短路径长度（记录每个节点的最短和次短距离）。
2. 根据次短路径长度，模拟红绿灯规则计算总时间。
🔍 步骤一：BFS 找次短路径长度
我们维护一个数组 dist[n+1][2]，其中：
- dist[i][0]：到节点 i 的最短距离
- dist[i][1]：到节点 i 的次短距离（严格大于最短）
初始化为 ∞，dist[1][0] = 0
使用队列进行 BFS（其实更像 Dijkstra，但由于边权为 1，BFS 即可）。
对每个出队的节点 u 和其邻居 v：
- 新距离 newDist = dist[u] + 1
- 如果 newDist dist[v][0] 且 newDist [] graph = new List[n + 1];
for (int i = 1; i ();
}
for (int[] e : edges) {
graph[e[0]].add(e[1]);
graph[e[1]].add(e[0]);
}
// dist[i][0] 最短, dist[i][1] 次短
int[][] dist = new int[n + 1][2];
for (int i = 1; i q = new LinkedList(); // [node, distance]
q.offer(new int[]{1, 0});
while (!q.isEmpty()) {
int[] cur = q.poll();
int u = cur[0], d = cur[1];
if (d > dist[u][1]) continue; // 已有更好的两个值
for (int v : graph[u]) {
int nd = d + 1;
if (nd dist[v][0] && nd < dist[v][1]) {
dist[v][1] = nd;
q.offer(new int[]{v, nd});
}
}
}
int secondShortest = dist[n][1]; // 第二短路径长度
// 模拟计算时间
long total = 0;
for (int i = 0; i < secondShortest; i++) {
if ((total / change) % 2 == 1) {
total = ((total / change) + 1) * change;
}
total += time;
}
return (int) total;
}
💡 示例说明
输入：
n = 5
edges = [[1,2],[1,3],[1,4],[3,4],[4,5]]
time = 3, change = 5
- 最短路径：1→4→5 （2 步）
- 第二短路径：1→3→4→5 或 1→2→...（但需连通），假设是 3 步
- 模拟 3 步的时间：
- step0: t=0 → 绿灯 → t=3
- step1: t=3 → 绿灯（3<5）→ t=6
- step2: t=6 → (6//5)=1 → 奇数 → 红灯！等至 10 → t=10+3=13
- 返回 13
📌 复杂度
- 时间：O(n + m)，BFS 每个节点最多入队两次（最短/次短）
- 空间：O(n + m)
如有需要，我也可以提供 Python 版本或进一步解释红绿灯逻辑！