问题

解决这样一类问题，起点不确定的，终点也不定的，可以有重边和自环的，各边权可能为负数的图的最短路问题

注意，图中一定不能有负权回路

要素

  1. g[][]邻接矩阵，存储图的信息，同时在程序结束后存储的就是各点间的最短距离

思路

本质上是基于动态规划，利用三角不等式 g[a][b] = Math.min(g[a][b], g[a][k] + g[k][b]
三重for循环搞定
时间复杂度：O(n^3)

状态表示：f[k][i][j]表示从i出发，最终走到j，且中间只经过节点编号不超过k的所有路径(类似于背包问题)路径长度的最小值
状态计算：
经过第k个节点f[k][i][j] = Math.min(f[k][i][j], f[k - 1][i][k] + f[k - 1][k][j])
不经过第k个节点f[k][i][j] = Math.min(f[k][i][j], f[k - 1][i][j])
去掉k所在维，结果不变，得到Floyed做法

模板

给定一个 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≤n2
1≤m≤20000,
图中涉及边长绝对值均不超过 10000。
输入样例：

  1. 3 3 2
  2. 1 2 1
  3. 2 3 2
  4. 1 3 1
  5. 2 1
  6. 1 3

输出样例：

  1. impossible
  2. 1
  1. import java.util.*;
  3. public class Main {
  4.     static int n, m;
  5.     static int[][] g;
  6.     public static void main(String[] args) {
  7.         Scanner sc = new Scanner(System.in);
  8.         n = sc.nextInt();
  9.         m = sc.nextInt();
  10.         int k = sc.nextInt();
  11.         g = new int[n + 1][n + 1];
  13.         // 初始化  
  14.         for (int i = 1; i<= n; i++) {
  15.             for (int j = 1; j <= n; j++) {
  16.                 if (i == j) g[i][j] = 0;
  17.                 else g[i][j] = 0x3f3f3f3f;
  18.             }
  19.         }
  21.         while (m-- > 0) {
  22.             int a, b, c;
  23.             a = sc.nextInt();
  24.             b = sc.nextInt();
  25.             c = sc.nextInt();
  27.             g[a][b] = Math.min(g[a][b], c);
  28.         }
  30.         floyd();
  32.         while (k-- > 0) {
  33.             int x = sc.nextInt();
  34.             int y = sc.nextInt();
  36.             if (g[x][y] > 0x3f3f3f3f / 2) System.out.println("impossible");
  37.             else System.out.println(g[x][y]);
  38.         }
  41.     }
  43.     static void floyd() {
  44.         for (int k = 1; k <= n; k++) {
  45.             for (int i = 1; i <= n; i++) {
  46.                 for (int j = 1; j <= n; j++) {
  47.                     g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
  48.                 }
  49.             }
  50.         }
  51.     }
  52. }

题型

  1. 最短路

    AcWing 1125. 牛的旅行
    思路：
    a. floyed求出任意两点之间的最短距离
    b. 求maxd[i]表示和i连通的且距离i最远的点的距离
    c. 枚举在哪两个边之间连边，i, j 且 dist[i][j] == INF
    maxd[i] + maxd[j] + d[i][j]
    d. res = Max(maxd[i], min(maxd[i] + maxd[j] + d[i][j]))

  2. 传递闭包

floyed-warshall算法 :::info 传递闭包：a->b->c，则为a, c之间连一条边：a -> c ::: AcWing 343. 排序

  1. 找最小环

spfa是找负环，Floyed是找最小的环(对于正权图来讲)
AcWing 344. 观光之旅
思路：
将所有环分类，依据环上编号最大的节点编号确定一个环
恰好就是floyed算法枚举的k，而i, j就是枚举环上直接和k相连的两条边，并且能保证枚举k时，dist[i, j]为只经过前k - 1个节点的最短路径
本题还有一个要求是输出最小环的所有节点，在更新最小环时，顺便记录该环的所有节点即可。
如何记录？利用图论的性质g[a][b] >= g[a][k] + g[k][b，递归找使得g[a][b] == g[a][k] + g[k][b]的点k即可。

  1. 恰好经过k条边的最短路

AcWing 345. 牛站
换一种DP的状态表示
f[k][i][j]从i到j恰好经过k条边的最短路径
结合快速幂
时间复杂度：O(N3logM)

  1. // 注意初始化 g[i][i]不能初始化为0
  3. import java.util.*;
  5. public class Main {
  6.     static final int N = 210, INF = 0x3f3f3f3f;
  7.     static int[][] g = new int[N][N], f = new int[N][N];
  8.     static int n, K, S, E, m;
  10.     public static void main(String[] args) {
  11.         Scanner sc = new Scanner(System.in);
  12.         K = sc.nextInt();
  13.         m = sc.nextInt();
  14.         S = sc.nextInt();
  15.         E = sc.nextInt();
  17.         for (int i = 1; i < N; i++)
  18.             for (int j = 1; j< N; j++)
  19.                     g[i][j] = INF;
  21.         Map<Integer, Integer> map = new HashMap<>();
  22.         for (int i = 0; i < m; i++) {
  23.             int w = sc.nextInt();
  24.             int a = sc.nextInt(), b = sc.nextInt();
  25.             if (!map.containsKey(a))
  26.                 map.put(a, ++n);
  27.             if (!map.containsKey(b))
  28.                 map.put(b, ++n);
  29.             a = map.get(a);
  30.             b = map.get(b);
  31.             g[a][b] = g[b][a] = Math.min(g[a][b], w);
  32.         }
  34.         qmi();
  35.         System.out.println(f[map.get(S)][map.get(E)]);
  36.     }
  38.     static void qmi() {
  39.         for (int i = 0; i < N; i++) {
  40.             Arrays.fill(f[i], INF);
  41.             f[i][i] = 0;
  42.         }
  43.         while (K > 0) {
  44.             if ((K & 1) == 1)
  45.                 mul(f, f, g);
  46.             K >>= 1;
  47.             mul(g, g, g);
  48.         }
  49.     }
  51.     static void mul(int[][] c, int[][] a, int[][] b) {
  52.         int[][] back = new int[n + 1][n + 1];
  53.         for (int i = 1; i <= n; i++)
  54.             Arrays.fill(back[i], INF);
  56.         for (int k = 1; k <= n; k++) {
  57.             for (int i = 1; i <= n; i++) {
  58.                 for (int j = 1; j <= n; j++) {
  59.                     back[i][j] = Math.min(back[i][j], a[i][k] + b[k][j]);
  60.                 }
  61.             }
  62.         }
  63.         for (int i = 1; i <= n; i++) {
  64.             for (int j = 1; j <= n; j++)
  65.                 c[i][j] = back[i][j];
  66.         }
  67.     }
  68. }