宫水三叶的刷题日记

V1

2023/01/11阅读:13主题:全栈蓝

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

题目描述

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

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

城市用一个 双向连通 图表示,图中有 个节点,从 编号(包含 )。图中的边用一个二维整数数组 表示,其中每个  表示一条节点  和节点  之间的双向连通边。每组节点对由 最多一条 边连通,顶点不存在连接到自身的边。穿过任意一条边的时间是  分钟。

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

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

  • 例如,[2, 3, 4] 中第二小的值是 ,而 [2, 2, 4] 中第二小的值是 。 给你 ,返回从节点 到节点 需要的 第二短时间 。

注意:

  • 你可以 任意次 穿过任意顶点,包括 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 分钟

提示:

  • 不含重复边
  • 每个节点都可以从其他节点直接或者间接到达

堆优化 Dijkstra

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

同时根据提示 可知,该图为「稀疏图」,容易想到「堆优化 Dijkstra」做法。

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

回到本题,与常规的「求最短路」不同,本题需要求得「严格次短路」,我们可以在原来的最短路算法基础上( 数组用于记录最短路)多引入一个 数组, 用于记录从节点 到节点 的严格次短路。

维护次短路是容易的,基本思路为:

  • 若当前距离 小于 ,原本的最短路 沦为次短路 ,即先用 更新 后,再用 更新
  • 若当前距离 等于 ,不符合「严格次短路」,忽略;
  • 若当前距离 大于 ,且 小于 ,则使用 更新

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

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

  • 为偶数:当前处于绿灯,动态边权为
  • 为奇数:当前处于红灯,需要增加动态边权(等待时间),增加的动态边权为 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[]{10});
        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];
    }
}
  • 时间复杂度:令 为点数, 为边数,堆优化 Dijkstra 的复杂度为
  • 空间复杂度:

BFS

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

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

代码:

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[]{10});
        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;
    }
}
  • 时间复杂度:令 为点数, 为边数,BFS 的复杂度为
  • 空间复杂度:

AStar 算法

BFS 的基础上再进一步,我们可以将问题拓展为「使用 AStar 算法来找第 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[]{10, 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 == 0return 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/SharingSource/LogicStack-LeetCode 。

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

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

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1