到达目的地的第二短时间
难度:
标签:
题目描述
城市用一个 双向连通 图表示，图中有 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 <= 104n - 1 <= edges.length <= min(2 * 104, n * (n - 1) / 2)edges[i].length == 21 <= ui, vi <= nui != vi- 不含重复边
- 每个节点都可以从其他节点直接或者间接到达
1 <= time, change <= 103
代码结果
运行时间: 238 ms, 内存: 22.8 MB
/*
This solution also uses Dijkstra's algorithm, but it utilizes Java Streams
to manage the priority queue and graph construction. The general logic remains
similar to the traditional approach, with additional stream-based operations.
*/
import java.util.*;
import java.util.stream.*;
public class SecondShortestPathStream {
static class Edge {
int node, time;
Edge(int node, int time) {
this.node = node;
this.time = time;
}
}
public int secondMinimum(int n, int[][] edges, int time, int change) {
List<List<Edge>> graph = IntStream.rangeClosed(0, n)
.mapToObj(i -> new ArrayList<Edge>())
.collect(Collectors.toList());
Arrays.stream(edges).forEach(edge -> {
graph.get(edge[0]).add(new Edge(edge[1], time));
graph.get(edge[1]).add(new Edge(edge[0], time));
});
int[][] dist = new int[n + 1][2];
Arrays.stream(dist).forEach(row -> Arrays.fill(row, Integer.MAX_VALUE));
dist[1][0] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
pq.offer(new int[]{0, 1, 0}); // time, node, count
while (!pq.isEmpty()) {
int[] curr = pq.poll();
int currTime = curr[0], currNode = curr[1], count = curr[2];
graph.get(currNode).stream().forEach(edge -> {
int nextNode = edge.node;
int nextTime = currTime + edge.time;
if ((nextTime / change) % 2 == 1) { // Waiting for green light
nextTime = (nextTime / change + 1) * change;
}
if (nextTime < dist[nextNode][0]) {
dist[nextNode][1] = dist[nextNode][0];
dist[nextNode][0] = nextTime;
pq.offer(new int[]{nextTime, nextNode, 0});
} else if (nextTime > dist[nextNode][0] && nextTime < dist[nextNode][1]) {
dist[nextNode][1] = nextTime;
pq.offer(new int[]{nextTime, nextNode, 1});
}
});
}
return dist[n][1];
}
}
解释
方法:
本题解采用广度优先搜索 (BFS) 算法来寻找从节点 1 到节点 n 的第二短路径时间。算法首先构建了一个邻接表 G 来表示图中的节点和边。然后，使用一个队列 q 来进行 BFS，其中队列中的每个元素是一个元组，包含当前节点编号和到达该节点的时间。时间 t1 根据当前时间和信号灯周期 change 计算，以决定是否需要等待红灯。如果当前时间 t 处于绿灯阶段，则直接加上通过时间 time；如果处于红灯阶段，则需等待至下一个绿灯开始，再加上通过时间。每遍历到一个新节点，如果该节点未被访问过，或者可以在更短的时间内到达，则更新到达时间并将其加入队列。算法的目标是找到第二短的到达时间，因此在到达节点 n 时，需要检查是否已有更短的路径存在，如果已经是第二次到达，则返回该时间作为结果。
时间复杂度:
O(V + E)
空间复杂度:
O(V + E)
代码细节讲解
🦆
在解题中你是如何考虑图中可能存在的环或重复路径对计算第二最短路径的影响？
▷🦆
BFS算法在处理节点访问时，通常不会重新访问已检查的节点。在这个解法中，你如何确保可以找到第二短路径而不是仅仅停留在最短路径的计算？
▷