【综合笔试题】难度 4.5/5，经典次短路问题

站长

2023年01月16日 21:00 · 阅读数 47

题目描述

这是 LeetCode 上的 2045. 到达目的地的第二短时间 ，难度为困难。

Tag : 「最短路」、「BFS」、「堆优化 Dijkstra」、「AStar 算法」、「启发式搜索」

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

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

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

例如，[2, 3, 4] 中第二小的值是 333 ，而 [2, 2, 4] 中第二小的值是 444 。给你 nnn、edgesedgesedges、timetimetime 和 changechangechange ，返回从节点 111 到节点 nnn 需要的第二短时间。

注意：

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

示例 1：【综合笔试题】难度 4.5/5，经典次短路问题

输入：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：【综合笔试题】难度 4.5/5，经典次短路问题

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

输出：11

解释：
最短时间路径是 1 -> 2 ，总花费时间 = 3 分钟
最短时间路径是 1 -> 2 -> 1 -> 2 ，总花费时间 = 11 分钟

提示：

2<=n<=1042 <= n <= 10^42<=n<=104
n−1<=edges.lengthn - 1 <= edges.lengthn−1<=edges.length <=min⁡(2×104,n×(n−1)2)<= \min(2 \times 10^4, \frac{n \times (n - 1)}{2})<=min(2×104,2n×(n−1))
edges[i].length==2edges[i].length == 2edges[i].length==2
1<=ui,vi<=n1 <= u_i, v_i <= n1<=ui,vi<=n
ui!=viu_i != v_iui!=vi
不含重复边
每个节点都可以从其他节点直接或者间接到达
1<=time,change<=1031 <= time, change <= 10^31<=time,change<=103

堆优化 Dijkstra

整体题意：在一张正权无向图上求严格次短路，该图无重边与自环。

同时根据提示 n−1<=edges.lengthn - 1 <= edges.lengthn−1<=edges.length <=min⁡(2×104,n×(n−1)2)<= \min(2 \times 10^4, \frac{n \times (n - 1)}{2})<=min(2×104,2n×(n−1)) 可知，该图为「稀疏图」，容易想到「堆优化 Dijkstra」做法。

对「堆优化 Dijkstra」或者「其他最短路算法」不熟悉的同学，可以看前置 🧀 ：【最短路/必背模板】涵盖所有的「存图方式」与「最短路算法（详尽注释）」。内容如题，首次接触的话，建议每个模板先敲十遍。

回到本题，与常规的「求最短路」不同，本题需要求得「严格次短路」，我们可以在原来的最短路算法基础上（dist1[]dist1[]dist1[] 数组用于记录最短路）多引入一个 dist2[]dist2[]dist2[] 数组，dist2[x]dist2[x]dist2[x] 用于记录从节点 111 到节点 xxx 的严格次短路。

维护次短路是容易的，基本思路为：

若当前距离 distdistdist 小于 dist1[x]dist1[x]dist1[x]，原本的最短路 dist1[x]dist1[x]dist1[x] 沦为次短路 dist2[x]dist2[x]dist2[x]，即先用 dist1[x]dist1[x]dist1[x] 更新 dist2[x]dist2[x]dist2[x] 后，再用 distdistdist 更新 dist1[x]dist1[x]dist1[x]；
若当前距离 distdistdist 等于 dist1[x]dist1[x]dist1[x]，不符合「严格次短路」，忽略；
若当前距离 distdistdist 大于 dist1[x]dist1[x]dist1[x]，且 distdistdist 小于 dist2[x]dist2[x]dist2[x]，则使用 distdistdist 更新 dist2[x]dist2[x]dist2[x]。

同时，由于处理「严格次短路包含重复边」的情况，我们无须使用 vis[]vis[]vis[] 数组记录处理过的点，而要确保每次「最短路」或者「次短路」被更新时，都进行入堆操作。

然后考虑「红绿灯」切换问题，这本质是引入动态边权，假设我们当前经过 stepstepstep 步到达节点 iii，根据其与 changechangechange 的关系分情况讨论即可：

⌊stepchange⌋\left \lfloor \frac{step}{change} \right \rfloor⌊changestep⌋ 为偶数：当前处于绿灯，动态边权为 000；
⌊stepchange⌋\left \lfloor \frac{step}{change} \right \rfloor⌊changestep⌋ 为奇数：当前处于红灯，需要增加动态边权（等待时间），增加的动态边权为 change - (step % change)。

最后，为了避免每个样例都 new 大数组，我们可以使用 static 修饰需要用到的数组，并在执行逻辑前进行重置工作。

代码：

class Solution {
    static int N = 10010, M = 4 * N, INF = 0x3f3f3f3f, idx = 0;
    static int[] he = new int[N], e = new int[M], ne = new int[M];
    static int[] dist1 = new int[N], dist2 = new int[N];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        idx++;
    }
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        Arrays.fill(dist1, INF);
        Arrays.fill(dist2, INF);
        Arrays.fill(he, -1);
        idx = 0;
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            add(u, v); add(v, u);
        }
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
        q.add(new int[]{1, 0});
        dist1[1] = 0;
        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int u = poll[0], step = poll[1];
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                int a = step / change, b = step % change;
                int wait = a % 2 == 0 ? 0 : change - b;
                int dist = step + time + wait;
                if (dist1[j] > dist) {
                    dist2[j] = dist1[j];
                    dist1[j] = dist;
                    q.add(new int[]{j, dist1[j]});
                    q.add(new int[]{j, dist2[j]});
                } else if (dist1[j] < dist && dist < dist2[j]) {
                    dist2[j] = dist;
                    q.add(new int[]{j, dist2[j]});
                }
            }
        }
        return dist2[n];
    }
}

时间复杂度：令 nnn 为点数，mmm 为边数，堆优化 Dijkstra 的复杂度为 O(mlog⁡n)O(m\log{n})O(mlogn)
空间复杂度：O(n+m)O(n + m)O(n+m)

BFS

更进一步，原图边权虽然由「固定部分 timetimetime」和「动态部分 changechangechange 相关」所组成，但在路径固定的前提下，其实边权之和完全确定。

因此我们可以先将原图等价为边权为 111 的新图，通过 BFS 求出最短路 dist1[x]dist1[x]dist1[x] 和严格次短路 dist2[x]dist2[x]dist2[x]，然后利用此时的 dist2[n]dist2[n]dist2[n] 其实是严格次短路的边数，计算原图上的边权之和。

代码：

class Solution {
    static int N = 10010, M = 4 * N, INF = 0x3f3f3f3f, idx = 0;
    static int[] he = new int[N], e = new int[M], ne = new int[M];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        idx++;
    }
    public int secondMinimum(int n, int[][] edges, int time, int change) {
        Arrays.fill(he, -1);
        idx = 0;
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            add(u, v); add(v, u);
        }
        Deque<int[]> d = new ArrayDeque<>();
        int[] dist1 = new int[n + 10], dist2 = new int[n + 10];
        Arrays.fill(dist1, INF);
        Arrays.fill(dist2, INF);
        d.addLast(new int[]{1, 0});
        dist1[1] = 0;
        while (!d.isEmpty()) {
            int[] poll = d.pollFirst();
            int u = poll[0], dist = poll[1];
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist1[j] > dist + 1) {
                    dist2[j] = dist1[j];
                    dist1[j] = dist + 1;
                    d.addLast(new int[]{j, dist1[j]});
                    d.addLast(new int[]{j, dist2[j]});
                } else if (dist1[j] < dist + 1 && dist + 1 < dist2[j]) {
                    dist2[j] = dist + 1;
                    d.addLast(new int[]{j, dist2[j]});
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < dist2[n]; i++) {
            int a = ans / change, b = ans % change;
            int wait = a % 2 == 0 ? 0 : change - b;
            ans += time + wait;
        }
        return ans;
    }
}

时间复杂度：令 nnn 为点数，mmm 为边数，BFS 的复杂度为 O(n+m)O(n + m)O(n+m)
空间复杂度：O(n+m)O(n + m)O(n+m)

AStar 算法

在 BFS 的基础上再进一步，我们可以将问题拓展为「使用 AStar 算法来找第 K 短路」（修改代码的 K 即可），利用终点的第 kkk 次出队必然是第 kkk 短路（注意要求的是严格的第 kkk 短路）。

代码：

class Solution {
    static int N = 10010, M = 4 * N, INF = 0x3f3f3f3f, K = 2, idx = 0, n = 0;
    static int[] he = new int[N], e = new int[M], ne = new int[M];
    static int[] dist = new int[N];
    void add(int a, int b) {
        e[idx] = b;
        ne[idx] = he[a];
        he[a] = idx;
        idx++;
    }
    void bfs() {
        Arrays.fill(dist, INF);
        Deque<Integer> d = new ArrayDeque<>();
        d.addLast(n);
        dist[n] = 0;
        while (!d.isEmpty()) {
            int x = d.pollFirst(), step = dist[x];
            for (int i = he[x]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] != INF) continue;
                dist[j] = step + 1;
                d.addLast(j);
            }
        }
    }
    int astar() {
        int k = K, min = -1;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[2]-b[2]);
        q.add(new int[]{1, 0, dist[1]});
        while (!q.isEmpty()) {
            int[] poll = q.poll();
            int x = poll[0], step = poll[1];
            if (x == n && min != step) {
                min = step;
                if (--k == 0) return min; 
            }
            for (int i = he[x]; i != -1; i = ne[i]) {
                int j = e[i];
                q.add(new int[]{j, step + 1, step + 1 + dist[j]});
            }
        }
        return -1; // never
    }
    public int secondMinimum(int _n, int[][] edges, int time, int change) {
        n = _n; idx = 0;
        Arrays.fill(he, -1);
        for (int[] e : edges) {
            int u = e[0], v = e[1];
            add(u, v); add(v, u);
        }
        bfs();
        int cnt = astar(), ans = 0;
        for (int i = 0; i < cnt; i++) {
            int a = ans / change, b = ans % change;
            int wait = a % 2 == 0 ? 0 : change - b;
            ans += time + wait;
        }
        return ans;
    }
}

时间复杂度：启发式搜索不讨论时空复杂度
空间复杂度：启发式搜索不讨论时空复杂度

最后

这是我们「刷穿 LeetCode」系列文章的第 No.2045 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的合集新基地 🎉🎉

转载自:https://juejin.cn/post/7187289315896983609