LeetCode编程题解法汇总|力扣解法汇总2045-到达目的地的第二短时间算法|动态规划|leetcode

原题链接：力扣
描述：城市用一个双向连通图表示，图中有 n 个节点，从 1 到 n 编号（包含 1 和 n）。图中的边用一个二维整数数组 edges 表示，其中每个 edges[i] = [ui, vi] 表示一条节点 ui 和节点 vi 之间的双向连通边。每组节点对由最多一条边连通，顶点不存在连接到自身的边。穿过任意一条边的时间是 time 分钟。
【LeetCode编程题解法汇总|力扣解法汇总2045-到达目的地的第二短时间】每个节点都有一个交通信号灯，每 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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/second-minimum-time-to-reach-destination
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路：

* 解题思路： * 广度搜索的题目， * 每一步，都有一个用时最短的方案。那么每一步，也都存在一种用时次短的方案。 * 所以记录每一个点最短和用时次短的方案，不断的递归找下去。

代码：

public class Solution2045 {public int secondMinimum(int n, int[][] edges, int time, int change) { List[] graph = new List[n + 1]; for (int i = 0; i <= n; i++) { graph[i] = new ArrayList(); } for (int[] edge : edges) { graph[edge[0]].add(edge[1]); graph[edge[1]].add(edge[0]); }// path[i][0] 表示从 1 到 i 的最短路长度，path[i][1] 表示从 1 到 i 的严格次短路长度 int[][] path = new int[n + 1][2]; for (int i = 0; i <= n; i++) { Arrays.fill(path[i], Integer.MAX_VALUE); } path[1][0] = 0; Queue queue = new ArrayDeque(); queue.offer(new int[]{1, 0}); while (path[n][1] == Integer.MAX_VALUE) { int[] arr = queue.poll(); int cur = arr[0], len = arr[1]; List integers = graph[cur]; for (int next : integers) { num++; if (len + 1 < path[next][0]) { path[next][0] = len + 1; queue.offer(new int[]{next, len + 1}); } else if (len + 1 > path[next][0] && len + 1 < path[next][1]) { path[next][1] = len + 1; queue.offer(new int[]{next, len + 1}); } } }int ret = 0; for (int i = 0; i < path[n][1]; i++) { if (ret % (2 * change) >= change) { ret = ret + (2 * change - ret % (2 * change)); } ret = ret + time; } System.out.println("num:" + num); return ret; }Integer minStep = null; Integer min2Step = Integer.MAX_VALUE; int[] cache = new int[10001]; Map> canSelect = new HashMap<>(); public int secondMinimum2(int n, int[][] edges, int time, int change) { for (int i = 0; i < edges.length; i++) { int[] edge = edges[i]; int i0 = edge[0]; int i1 = edge[1]; Set integers = canSelect.get(i0); if (integers == null) { integers = new HashSet<>(); canSelect.put(i0, integers); } integers.add(i1); integers = canSelect.get(i1); if (integers == null) { integers = new HashSet<>(); canSelect.put(i1, integers); } integers.add(i0); }HashSet firstLevel = new HashSet<>(); firstLevel.add(n); searchChange(n, firstLevel); //计算一下时间就好 min2Step = Math.min(min2Step, minStep + 2); //计算时间 int currentTime = 0; int currentIndex = 0; while (true) { currentTime += time; int i = currentTime / change; if (++currentIndex >= min2Step) { break; } if (i % 2 == 1) { currentTime = (i + 1) * change; }} System.out.println("num:" + num); return currentTime; }int num = 0; //改为非递归 private void searchChange(int n, Set levelSelectSet) { int stepLevel = 0; cache[n] = 2; while (true) { if (stepLevel >= n) { break; } if (levelSelectSet.contains(1)) { if (minStep == null) { minStep = stepLevel; } else if (stepLevel > minStep) { min2Step = stepLevel; break; } } levelSelectSet.remove(1); Set nextSelectSet = new HashSet<>(); int[] cacheLocal = new int[n + 1]; System.arraycopy(cache, 0, cacheLocal, 0, n); for (Integer select : levelSelectSet) { Set canSelectSet = canSelect.get(select); for (int i : canSelectSet) { num++; //最优解，一个数字超过2次则不需要添加 if (cache[i] == 2) { continue; } if (cache[i] == 1) { cacheLocal[i] = 2; } else { cacheLocal[i] = 1; } nextSelectSet.add(i); } } cache = cacheLocal; levelSelectSet = nextSelectSet; stepLevel++; } } }