乐趣区

关于后端:综合笔试题难度-455经典次短路问题

jiezi

题目形容

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

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

城市用一个 双向连通 图示意，图中有 $n$ 个节点，从 $1$ 到 $n$ 编号（蕴含 $1$ 和 $n$）。图中的边用一个二维整数数组 $edges$ 示意，其中每个 $edges[i] = [u_i, v_i]$ 示意一条节点 $u_i$ 和节点 $v_i$ 之间的双向连通边。每组节点对由 最多一条 边连通，顶点不存在连贯到本身的边。穿过任意一条边的工夫是 $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 <= 10^4$
  • $n – 1 <= edges.length$ $<= \min(2 \times 10^4, \frac{n \times (n – 1)}{2})$
  • $edges[i].length == 2$
  • $1 <= u_i, v_i <= n$
  • $u_i != v_i$
  • 不含反复边
  • 每个节点都能够从其余节点间接或者间接达到
  • $1 <= time, change <= 10^3$

堆优化 Dijkstra

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

同时依据提醒 $n – 1 <= edges.length$ $<= \min(2 \times 10^4, \frac{n \times (n – 1)}{2})$ 可知，该图为「稠密图」，容易想到「堆优化 Dijkstra」做法。

对「堆优化 Dijkstra」或者「其余最短路算法」不相熟的同学，能够看前置 🧀：【最短路 / 必背模板】涵盖所有的「存图形式」与「最短路算法（详尽正文）」。内容如题，首次接触的话，倡议每个模板先敲十遍。

回到本题，与惯例的「求最短路」不同，本题须要求得「严格次短路」，咱们能够在原来的最短路算法根底上（$dist1[]$ 数组用于记录最短路）多引入一个 $dist2[]$ 数组，$dist2[x]$ 用于记录从节点 $1$ 到节点 $x$ 的严格次短路。

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

  • 若以后间隔 $dist$ 小于 $dist1[x]$，本来的最短路 $dist1[x]$ 沦为次短路 $dist2[x]$，即先用 $dist1[x]$ 更新 $dist2[x]$ 后，再用 $dist$ 更新 $dist1[x]$；
  • 若以后间隔 $dist$ 等于 $dist1[x]$，不合乎「严格次短路」，疏忽；
  • 若以后间隔 $dist$ 大于 $dist1[x]$，且 $dist$ 小于 $dist2[x]$，则应用 $dist$ 更新 $dist2[x]$。

同时，因为解决「严格次短路蕴含反复边」的状况，咱们毋庸应用 $vis[]$ 数组记录解决过的点，而要确保每次「最短路」或者「次短路」被更新时，都进行入堆操作。

而后思考「红绿灯」切换问题，这实质是引入动静边权，假如咱们以后通过 $step$ 步达到节点 $i$，依据其与 $change$ 的关系分状况探讨即可：

  • $\left \lfloor \frac{step}{change} \right \rfloor$ 为偶数：以后处于绿灯，动静边权为 $0$；
  • $\left \lfloor \frac{step}{change} \right \rfloor$ 为奇数：以后处于红灯，须要减少动静边权（等待时间），减少的动静边权为 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];
    }
}
  • 工夫复杂度：令 $n$ 为点数，$m$ 为边数，堆优化 Dijkstra 的复杂度为 $O(m\log{n})$
  • 空间复杂度：$O(n + m)$

BFS

更进一步，原图边权尽管由「固定局部 $time$」和「动静局部 $change$ 相干」所组成，但在门路固定的前提下，其实边权之和齐全确定。

因而咱们能够先将原图等价为边权为 $1$ 的新图，通过 BFS 求出最短路 $dist1[x]$ 和严格次短路 $dist2[x]$，而后利用此时的 $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;
    }
}
  • 工夫复杂度：令 $n$ 为点数，$m$ 为边数，BFS 的复杂度为 $O(n + m)$
  • 空间复杂度：$O(n + m)$

AStar 算法

在 BFS 的根底上再进一步，咱们能够将问题拓展为「应用 AStar 算法来找第 K 短路」（批改代码的 K 即可），利用起点的第 $k$ 次出队必然是第 $k$ 短路（留神要求的是严格的第 $k$ 短路）。

代码：

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 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

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

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

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

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉

本文由 mdnice 多平台公布

退出移动版