Bellman Ford

问题

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

注意：求起点到终点的最短路，这两点中间不能有负权回路，这样会导致负无穷（限制边数除外，一定有解） 给定起点和终点，有负环的图可能有最短路，没有负环的图一定有最短路

要素

1. 既不需要用邻接矩阵，也不需要邻接表，只要能把每条边的信息存下来就行，因为整个过程只需要循环遍历每条边即可

   class Edge {
    int a, b, w;
    Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
   }

2. dist[] 存储每个点到起点的最短距离

3. back[] 存储上一轮 dist[] 的信息，用于更新该轮dist[]

   思路

for()k次，k指被限制的边数大小

限制边数为k，即求从起点到终点最多经过k条边的最短距离 如果k = n，在第n次循环中如果dist还有更新说明负环存在！

for(所有边)
dist[b] = min(dist[b], dist[a] + w 松弛操作
a 指边的起点， b 指边的终点， w 指边权

循环结束后，所有边满足 dist[b] <= dist[a] + w

时间复杂度：O(K * M)
本质：DP

模板

853. 有边数限制的最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环， 边权可能为负数。
请你求出从 1 号点到 n 号点的最多经过 k 条边的最短距离，如果无法从 1 号点走到 n 号点，输出 impossible。
最多经过 k 条边 等价于 最多经过 k - 1个中转点(不包含起点)
注意：图中可能 存在负权回路 。
输入格式
第一行包含三个整数 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

import java.util.*;
public class Main {
    static final int N = 510, M = 10010, INF = 0x3f3f3f3f;
    static Edge[] edges = new Edge[M];
    static int n, m, k;
    static int[] dist = new int[N];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            edges[i] = new Edge(a, b, c);
        }
        ford(1, k, dist);
        if (dist[n] > INF / 2)
            System.out.println("impossible");
        else
            System.out.println(dist[n]);
    }
    static void ford(int start, int k, int[] dist) {
        Arrays.fill(dist, INF);
        dist[start] = 0;
        int[] back = new int[N];
        for (int i = 1; i <= k; i++) {
            System.arraycopy(dist, 1, back, 1, n);
            for (int j = 0; j < m; j++) {
                int a = edges[j].a, b = edges[j].b, c = edges[j].c;
                dist[b] = Math.min(dist[b], back[a] + c);
            }
        }
    }
}
class Edge {
    int a, b, c;
    Edge(int a, int b, int c) {
        this.a = a;
        this.b = b;
        this.c = c;
    }
}