目录

图论:常见的最短路算法模板

849. Dijkstra 求最短路 I

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,所有边权均为正值。

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出-1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出-1。

数据范围: $1≤n≤500, 1≤m≤10^5$ , 图中涉及边长均不超过 10000。

进阶: $1≤n,m≤1.5×10^5$ , 图中涉及边长均不超过 10000。

输入样例:

3 3
1 2 2
2 3 1
1 3 4

输出样例:

3

解法一

Dijkstra 适用于非负权图,其核心思路就是将所有的点划分为两部分,一部分是已经确定最短路的点集合 $p$ ,这个集合最开始只有源点。另一部分是未确定最短路的点集合 $q$ 。

  1. 首先将刚加入 $p$ 的点的所有出边进行松弛(最开始就只有源点 $s$ )
  2. 然后在 $q$ 中找一个离源点 $s$ 最近的,那么这个点的最短路就确定了,因为这个点当前的最短路必然是经过 $p$ 集合中的点进行松弛过后的,且图没有负权,所以这个点不可能再通过其他未确定的点中转来缩短距离(如果有负权就可能,所以 Dijkstra 无法处理存在负权的图),将其标记进入 $p$ 集合,然后重复步骤一,直到所有点都加入 $p$ 集合

Dijkstra 暴力写法,这题题目数据范围比较小 $n<500$ ,所以直接建邻接矩阵然后跑 Dijkstra,时间复杂度 $O(N^2)$

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] in = read(br);
        int N = in[0], M = in[1];
        //邻接矩阵
        int[][] w = new int[N][N];
        for (int i = 0; i < N; i++) {
            Arrays.fill(w[i], INF);
        }
        for (int i = 0; i < M; i++) {
            int[] t = read(br); //t[0]->t[1]
            int x = t[0]-1, y = t[1]-1;
            w[x][y] = Math.min(t[2], w[x][y]);
        }
        //dis[i]: 源点 s 到 i 的最短距离
        int[] dis = new int[N];
        boolean[] vis = new boolean[N];
        Arrays.fill(dis, INF);
        dis[0] = 0;
        for (int i = 0; i < N; i++) {
            int min = -1;
            //未确定最短路的点中距离 s 最近的点
            for (int j = 0; j < N; j++) {
                if (!vis[j] && (min==-1 || dis[j] < dis[min])) {
                    min = j;
                }
            }
            //松弛
            vis[min] = true;
            for (int j = 0; j < N; j++) {
                if (!vis[j]) {
                    dis[j] = Math.min(dis[j], dis[min] + w[min][j]);
                }
            }
        }
        out.println(dis[N-1] == INF ? -1 : dis[N-1]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

解法二

堆优化的 Dijkstra,上面的解法在数据量大的时候显然是不适用的,首先我们不能再使用邻接矩阵了,需要改用邻接表,同时采用小根堆来快速的获取未确定点集中距离源点最近的点,堆中需要存储节点编号以及当前节点最短路,时间复杂度大概 $O(m\log n)$ ,但是最坏情况下 $m$ 边数可能会达到 $n^2$ 级别(稠密图),导致堆优化的复杂度反而低于朴素的,但是大多数情况下边数不会有这么多,除此之外还有一些其它的优化方法,详见 OI-Wiki

import java.util.*;
import java.io.*;

class Main {

    static class Node {
        int idx, val;
        public Node(int idx, int val) {
            this.idx = idx;
            this.val = val;
        }
    }

    static int idx;
    static int N, M;
    static int[] h, e, ne, w;
    //a->b
    static void add(int a, int b, int c) {
        w[idx] = c; e[idx] = b; 
        ne[idx] = h[a]; h[a] = idx++;
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] in = read(br);
        N = in[0]; M = in[1];
        h = new int[N+1]; e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
        Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0], t[1], t[2]);
        }
        PriorityQueue<Node> pq = new PriorityQueue<>((n1, n2)->n1.val-n2.val);
        int[] dis = new int[N+1];
        //记录已经确定最短路的点集 s
        boolean[] vis = new boolean[N+1];
        Arrays.fill(dis, INF);
        dis[1] = 0;
        pq.add(new Node(1, 0));
        while (!pq.isEmpty()) {
            Node node = pq.poll();
            //从未确定最短路的点中找 dis 最小的(如果弹出来的是已经确定过的就会跳过)
            int i = node.idx, v = node.val;
            if (vis[i]) continue;
            //标记该点已经确定最短路
            vis[i] = true;
            //松弛该点出边
            for (int j = h[i]; j != -1; j = ne[j]) {
                if (v+w[j] < dis[e[j]]) {
                    dis[e[j]] = v+w[j];
                    pq.add(new Node(e[j], v+w[j]));
                }
            }
        }
        out.println(dis[N] == INF ? -1 : dis[N]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

Java 其实还有一种更加简洁的写法,利用闭包,不用新建 Node 类

import java.util.*;
import java.io.*;

class Main {

    static int idx;
    static int N, M;
    static int[] h, e, ne, w;
    //a->b
    static void add(int a, int b, int c) {
        w[idx] = c; e[idx] = b; 
        ne[idx] = h[a]; h[a] = idx++;
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] in = read(br);
        N = in[0]; M = in[1];
        h = new int[N]; e = new int[M]; ne = new int[M]; w = new int[M];
        Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0]-1, t[1]-1, t[2]);
        }
        int[] dis = new int[N];
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b)->dis[a]-dis[b]);
        //记录已经确定最短路的点集 s
        boolean[] vis = new boolean[N];
        Arrays.fill(dis, INF);
        dis[0] = 0;
        pq.add(0);
        while (!pq.isEmpty()) {
            int i = pq.poll();
            if (vis[i]) continue;
            //标记该点已经确定最短路
            vis[i] = true;
            //松弛该点能到达的点的 dis
            for (int j = h[i]; j != -1; j = ne[j]) {
                if (dis[i]+w[j] < dis[e[j]]) {
                    dis[e[j]] = dis[i]+w[j];
                    pq.add(e[j]);
                }
            }
        }
        out.println(dis[N-1] == INF ? -1 : dis[N-1]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

853. 有边数限制的最短路

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。

请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离,如果无法从 1 号点走到 n 号点,输出 impossible。

注意:图中可能存在负权回路

输入格式

第一行包含三个整数 n,m,k。

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示从 1 号点到 n 号点的最多经过 k 条边的最短距离。

如果不存在满足条件的路径,则输出“impossible”。

数据范围: $1≤n,k≤500, 1≤m≤10000$ ,且任意边长的绝对值不超过 $10000$

输入样例:

3 3 1
1 2 1
2 3 1
1 3 3

输出样例:

3

解法一

Bellman−Ford,负权最短路算法,可以处理负权边,同时可以检测负权回路(回路的总权值为负数)。算法基于动态规划设计, $dis[i][j]$ 为源点 $s$ 经过最多 $i$ 条边到达 $j$ 节点的最短路。一共有 $N$ 个点,所以任意点的最短路最多经过的边数为 $N-1$ (负环没有最短路)

  • 入口: $dis[i][s] = 0, 0 \leq i \leq N-1$
  • 转移:遍历所有的边, $k \stackrel{w}{\longrightarrow} j$ , $dis[i][j] = \min(dis[i-1][j],dis[i][j], dis[i-1][k] + w)$
  • 出口: $dis[N-1][N]$
  • 时间复杂度: $O(MN)$

本题中限制了边数,所以我们外层循环只到 $K$ 就行了,具体代码实现如下:

import java.util.*;
import java.io.*;

class Main {

    static class Edge {
        int s, e;
        int v;
        public Edge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int INF = 0x3f3f3f3f;
        int N = in[0], M = in[1], K = in[2];
        Edge[] eds = new Edge[M];
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            eds[i] = new Edge(t[0], t[1], t[2]);
        }
        int[][] dis = new int[K+1][N+1];
        for (int i = 0; i <= K; i++) {
            Arrays.fill(dis[i], INF);
            dis[i][1] = 0;
        }
        for (int i = 1; i <= K; i++) {
            for (int j = 0; j < M; j++) {
                int s = eds[j].s, e = eds[j].e;
                if (dis[i-1][s] == INF) continue;
                // 不加 dis[i-1][e] 也能过 OJ,但是最好还是加上
                // dis[i][e] = Math.min(dis[i][e], dis[i-1][s] + eds[j].v); 
                dis[i][e] = Math.min(dis[i-1][e], Math.min(dis[i][e], dis[i-1][s] + eds[j].v));
            }
        }
        out.println(dis[K][N] == INF ? "impossible" : dis[K][N]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

这里存个疑问,为什么这里转移方程不加 $dis[i-1][e]$ 也能 AC?这里加上一定不会错,但是不加会有点迷惑。

这里我的想法是,如果不加 $dis[i-1][e]$ ,状态的定义其实就变成了:恰好经过 $i$ 条边的时候的最短路,这样出口就是 $\min(dp[1\sim M][N])$ ,但是由于我们在入口定义了 $dp[1\sim M][s]=0$ ,误打误撞的导致出口变成了 $dp[M][N]$ ,具体原因不想深究,明白错哪里就行了,总之这是一种不伦不类的写法,不要这样写,正确写法如下:

状态定义为恰好经过 i 条边的写法
import java.util.*;
import java.io.*;

class Main {

    static class Edge {
        int s, e;
        int v;
        public Edge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int INF = 0x3f3f3f3f;
        int N = in[0], M = in[1], K = in[2];
        Edge[] eds = new Edge[M];
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            eds[i] = new Edge(t[0], t[1], t[2]);
        }
        //恰好经过 i 条边
        int[][] dis = new int[K+1][N+1];
        for (int i = 0; i <= K; i++) {
            Arrays.fill(dis[i], INF);
        }
        dis[0][1] = 0;
        for (int i = 1; i <= K; i++) {
            for (int j = 0; j < M; j++) {
                int s = eds[j].s, e = eds[j].e;
                if (dis[i-1][s] == INF) continue;
                dis[i][e] = Math.min(dis[i][e], dis[i-1][s] + eds[j].v);
            }
        }
        int res = INF;
        for (int i = 0; i <= K; i++) {
            res = Math.min(res, dis[i][N]);
        }
        out.println(res == INF ? "impossible" : res);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

解法二

实际中通常写的都是一维的 Bellman−Ford,降维后在 $dis[e] = \min(dis[e],dis[s] + w)$ 中, $dis[s]$ 不仅包含了前一轮最多经过 $i-1$ 条边到达 $s$ 的最短路,同时也包含了当前轮最多经过 $i$ 条边到达 $s$ 的最短路,所以最终经过 $k$ 次松弛得到的结果 $dis[N]$ 可能不只经过了 $k$ 条边,所以在这题中我们需要保存一下上一轮的状态,用上一轮的 $dis[s]$ 来更新当前轮的 $dis[e]$ ,保证最后结果经过的边不超过 $K$

import java.util.*;
import java.io.*;

class Main {

    static class Edge {
        int s, e;
        int v;
        public Edge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int INF = 0x3f3f3f3f;
        int N = in[0], M = in[1], K = in[2];
        Edge[] eds = new Edge[M];
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            eds[i] = new Edge(t[0]-1, t[1]-1, t[2]);
        }
        //dis[i][j]: 源点最多经过 i 条边,到达 j 点的最短路
        int[] dis = new int[N];
        //上一轮经过 (i-1) 次松弛后的结果,避免串联更新(当前轮更新当前轮),因为这题需要保证最多只能经过 K 条边
        int[] last = new int[N];
        Arrays.fill(dis, INF);
        dis[0] = 0;
        for (int i = 0; i < K; i++) {
            System.arraycopy(dis, 0, last, 0, N);
            for (int j = 0; j < M; j++) {
                int s = eds[j].s, e = eds[j].e;
                if (last[s] == INF) continue;
                dis[e] = Math.min(dis[e], last[s] + eds[j].v);
            }
        }
        out.println(dis[N-1] == INF ? "impossible" : dis[N-1]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

如果数据量比较大可以改成 SPFA,如下:

import java.util.*;
import java.io.*;

class Main {
    
    static int idx;
    static int N, M, K;
    static int[] h, e, ne, w;
    //a->b
    static void add(int a, int b, int c) {
        w[idx] = c; e[idx] = b; 
        ne[idx] = h[a]; h[a] = idx++;
    }
        
    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] in = read(br);
        int INF = 0x3f3f3f3f;
        N = in[0]; M = in[1]; K = in[2];
        e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
        h = new int[N+1]; Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0], t[1], t[2]);
        }
        //恰好经过 i 条边到达 j 的最短路
        int[][] dis = new int[K+1][N+1];
        boolean[][] vis = new boolean[K+1][N+1];
        for (int i = 0; i <= K; i++) {
            Arrays.fill(dis[i], INF);
        }
        dis[0][1] = 0; vis[0][1] = true;
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{1, 0});
        while (!queue.isEmpty()) {
            int[] top = queue.poll();
            int i = top[0], step = top[1];
            if (step >= K) continue;
            vis[step][i] = false;
            for (int j = h[i]; j != -1; j = ne[j]) {
                int k = e[j];
                if (w[j]==INF || dis[step][i]==INF) continue;
                if (dis[step+1][k] > dis[step][i] + w[j]) {
                    dis[step+1][k] = dis[step][i] + w[j];
                    if (!vis[step+1][k]) {
                        queue.add(new int[]{k, step+1});
                        vis[step+1][k] = true;
                    }
                }
            }
        }
        int res = INF;
        for (int i = 0; i <= K; i++) {
            res = Math.min(res, dis[i][N]);
        }
        out.println(res==INF ? "impossible" : res);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

851. spfa 求最短路

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数

请你求出 1 号点到 n 号点的最短距离,如果无法从 1 号点走到 n 号点,则输出 impossible。数据保证不存在负权回路

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

输出一个整数,表示 1 号点到 n 号点的最短距离。

如果路径不存在,则输出”impossible”。

数据范围: $1≤n,m≤105$ ,图中涉及边长绝对值均不超过 10000。

输入样例:

3 3
1 2 5
2 3 -3
1 3 4

输出样例:

2

解法一

SPFA 基于 Bellman−Ford 进行优化,最坏时间复杂度依然是 $O(MN)$ ,但是常规情况下速度还是很快的,时间复杂度不稳定。

优化的点在于 BF 在松弛过程中有一些顶点可能早已经得到了最短路,后续不会再被松弛,但是依然会进行判断,浪费了时间,所以我们可以考虑只对最短路估计值减小了的顶点的出边进行松弛

具体实现中,我们可以采用一个 FIFO 队列存储松弛成功的顶点,最开始就只有源点 $s$ ,入队的顶点需要进行标记,对队列中顶点的出边进行松弛,将松弛成功并且没有标记的顶点继续加入队列。乍一看和 BFS 类似,但是这里其实有一个很大的区别:SPFA 在队首元素出队后需要将其标记取消,因为队首顶点后续可能还会被其他顶点松弛,这也是 SPFA 时间复杂度不稳定的原因(容易被卡,但是最差也是退化到 $O(NM)$ )。

import java.util.*;
import java.io.*;

class Main {

    static int idx;
    static int[] e, h, ne, w;
    //a->b
    public static void add(int a, int b, int c){
        e[idx] = b; w[idx] = c;
        ne[idx] = h[a]; h[a] = idx++;
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int INF = 0x3f3f3f3f;
        int[] in = read(br);
        int N = in[0], M = in[1];
        e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
        h = new int[N+1]; Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0], t[1], t[2]);
        }
        Queue<Integer> queue = new LinkedList<>();
        boolean[] vis = new boolean[N+1];
        int[] dis = new int[N+1];
        Arrays.fill(dis, INF);
        dis[1] = 0; vis[1] = true;
        queue.add(1);
        while (!queue.isEmpty()) {
            int top = queue.poll();
            vis[top] = false;
            for (int i = h[top]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dis[j] > dis[top] + w[i]) {
                    dis[j] = dis[top] + w[i];
                    if (!vis[j]) {
                        queue.add(j);
                        vis[j] = true;
                    }
                }
            }
        }
        out.println(dis[N] == INF ? "impossible" : dis[N]);
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

852. spfa 判断负环

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环, 边权可能为负数。请你判断图中是否存在负权回路。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

输出格式

如果图中存在负权回路,则输出“Yes”,否则输出“No”。

数据范围: $1≤n≤2000,1≤m≤10000$ ,图中涉及边长绝对值均不超过 10000。

输入样例:

3 3
1 2 -1
2 3 4
3 1 -4

输出样例:

Yes

解法一

题目是判断图有没有负环,但是图不一定是联通的,单纯从某个点出发并不一定能走到负环上,暴力的方法就是对每个点作为源点做一次 spfa,但是这样显然复杂度过高

考虑增加一个虚拟节点,和所有的点增加一条权值为 0 的单向边,新增加的虚拟节点一定能走到负环上,所以我们对虚拟节点做一次 spfa 就能判断出原图是否有负环 https://static.imlgw.top/blog/20210317/eYBzmdAcyRL7.png 模拟第一次入队出队,虚拟节点出队后就会将所有的节点入队, $dis[i]$ 为虚拟源点到当前节点的最短路,所以一开始所有的 $dis[v_i]=0$ ,不用初始化为 $\inf$ 。

然后就是关键的判环步骤,我们只需要记录下每个点到虚拟源点的边的数量就行了(初始 $cnt[v_i]=1$ ),如果有负环就会无限制的松弛负环上的边,在负环路上打转,所以如果松弛后某个点到虚拟源点的边的数量大于等于 $N+1$ 就说明存在负环

import java.util.*;
import java.io.*;

class Main {

    static int INF = 0x3f3f3f3f;
    static int N, M;
    static int idx;
    static int[] e, h, ne, w;
    //a->b
    public static void add(int a, int b, int c){
        e[idx] = b; w[idx] = c;
        ne[idx] = h[a]; h[a] = idx++;
    }

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        N = in[0]; M = in[1];
        e = new int[M+1]; ne = new int[M+1]; w = new int[M+1];
        h = new int[N+1]; Arrays.fill(h, -1);
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            add(t[0], t[1], t[2]);
        }
        out.println(spfa() ? "Yes" : "No");
        out.flush();
    }

    public static boolean spfa() {
        Queue<Integer> queue = new LinkedList<>();
        int[] dis = new int[N+1];
        boolean[] vis = new boolean[N+1];
        int[] cnt = new int[N+1];
        for (int i = 1; i <= N; i++) {
            queue.add(i);
            vis[i] = true;
            cnt[i] = 1;
        }
        while (!queue.isEmpty()) {
            int top = queue.poll();
            vis[top] = false;
            for (int i = h[top]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dis[j] > dis[top] + w[i]) {
                    dis[j] = dis[top] + w[i];
                    cnt[j] = cnt[top] + 1;
                    if (cnt[j] >= N+1) return true;
                    if (!vis[j]) {
                        queue.add(j);
                        vis[j] = true;
                    }
                }
            }
        }
        return false;
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

854. Floyd 求最短路

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环,边权可能为负数。

再给定 k 个询问,每个询问包含两个整数 x 和 y,表示查询从点 x 到点 y 的最短距离,如果路径不存在,则输出“impossible”。

数据保证图中不存在负权回路。

输入格式

第一行包含三个整数 n,m,k

接下来 m 行,每行包含三个整数 x,y,z,表示存在一条从点 x 到点 y 的有向边,边长为 z。

接下来 k 行,每行包含两个整数 x,y,表示询问点 x 到点 y 的最短距离。

输出格式

共 k 行,每行输出一个整数,表示询问的结果,若询问两点间不存在路径,则输出“impossible”。

数据范围: $1≤n≤200,1≤k≤n^2,1≤m≤20000$ , 图中涉及边长绝对值均不超过 10000。

输入样例:

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例:

impossible
1

解法一

Floyd 是一个多源的最短路算法,也就是可以同时求出图中任意两点之间的最短路,本质是一个 DP,时间复杂度较高

  • 状态定义: $dis[k][i][j]$ ,从 $i$ 到 $j$ 经过前 $k$ 个点中转后的最短路
  • 入口: $dis[0][i][i]=0,dis[0][i][j] = w_{ij}$
  • 转移: $dis[k][i][j]=\min(dis[k-1][i][j],dis[k-1][i][k]+dis[k-1][k][j])$
  • 出口: $dis[N][i][j]$ ,时间复杂度 $O(N^3)$

由于 $dis[k]$ 仅仅依赖 $dis[k-1]$ ,所以通常我们这里都会降维写二维的

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int N = in[0], M = in[1], K = in[2];
        int INF = 0x3f3f3f3f;
        int[][] dis = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dis[i], INF);
            dis[i][i] = 0;
        }
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            int x = t[0], y = t[1];
            dis[x][y] = Math.min(dis[x][y], t[2]);
        }
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dis[i][k] == INF || dis[k][j] == INF) continue;
                    dis[i][j] = Math.min(dis[i][j], dis[i][k] + dis[k][j]);
                }
            }
        }
        for (int i = 0; i < K; i++) {
            int[] q = read(br);
            int res = dis[q[0]][q[1]];
            out.println(res == INF ? "impossible" : res);
        }
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}

三维的写法:854. Floyd 求最短路 三维 DP 写法,不降维

import java.util.*;
import java.io.*;

class Main {

    public static void main(String... args) throws Exception {
        PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // BufferedReader br = new BufferedReader(new InputStreamReader(new FileInputStream("./input.txt")));
        int[] in = read(br);
        int N = in[0], M = in[1], K = in[2];
        int INF = 0x3f3f3f3f;
        int[][][] dis = new int[N+1][N+1][N+1];
        for (int i = 1; i <= N; i++) {
            Arrays.fill(dis[0][i], INF);
            dis[0][i][i] = 0;
        }
        for (int i = 0; i < M; i++) {
            int[] t = read(br);
            int x = t[0], y = t[1];
            dis[0][x][y] = Math.min(dis[0][x][y], t[2]);
        }
        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (dis[k-1][i][k] == INF || dis[k-1][k][j] == INF) {
                        dis[k][i][j] = dis[k-1][i][j];
                    } else {
                        dis[k][i][j] = Math.min(dis[k-1][i][j], dis[k-1][i][k] + dis[k-1][k][j]);   
                    }
                }
            }
        }
        for (int i = 0; i < K; i++) {
            int[] q = read(br);
            int res = dis[N][q[0]][q[1]];
            out.println(res == INF ? "impossible" : res);
        }
        out.flush();
    }

    public static int[] read(BufferedReader br) throws Exception {
        return Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    }
}