AcWing 853. 有边数限制的最短路（bellman - ford）

题目

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

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

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

输入格式

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

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

点的编号为 1～n。

输出格式

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

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

数据范围

1≤n,k≤500
1≤m≤10000
1≤x,y≤n
任意边长的绝对值不超过 10000。

输入样例：

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

输出样例：

3

代码与思路

这道题的关键点是负权边+ 有限边，这篇题解写的很好，所以不能用Dijkstra算法去算

同时附上补充：

Dijkstra算法和Bellman-Ford算法都可以解决单源最短路径问题，但它们在处理负权边的情况下有不同的适用性和限制。

Dijkstra算法的前提是图中不能有负权边，因为它基于贪心策略，每次选择当前距离最短的节点进行松弛操作。如果存在负权边，那么可能会导致在负权环中无限松弛下去，使算法无法终止。

Bellman-Ford算法允许图中存在负权边，并且能够检测出图中是否存在负权环。它通过对所有边进行松弛操作的方式，进行多轮迭代来逐步逼近最短路径。在一般情况下，Bellman-Ford算法的时间复杂度较高，为O(V * E)，其中V为节点数，E为边数。但是由于其适用性更广泛，可以处理带负权边的情况，而Dijkstra算法不能处理负权边，所以在一些特殊情况下，Bellman-Ford算法是更合适的选择。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, m, k, N = 510, Ma = 0x3f3f3f3f, M = 10010;
    static int[] dis = new int[N], copyArray = new int[N];
    static Edge[] e = new Edge[M];

    public static class Edge {
        int a, b, w;

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

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();

        for (int i = 0; i < m; i++) {
            int x = in.nextInt();
            int y = in.nextInt();
            int z = in.nextInt();
            e[i] = new Edge(x, y, z);
        }
        bellmanFord();
        if (dis[n] > Ma / 2) {
            System.out.println("impossible");
        } else {
            System.out.println(dis[n]);
        }
    }

    /**
     * Bellman-Ford算法求最短路径
     */
    private static void bellmanFord() {
        Arrays.fill(dis, Ma); // 初始化距离数组为最大值
        dis[1] = 0; // 起点到自身的距离为0
        for (int i = 0; i < k; i++) {  // 只能走k条边
            System.arraycopy(dis, 0, copyArray, 0, dis.length);  // 备份当前的距离数组
            for (int j = 0; j < m; j++) {
                Edge ne = e[j];  // 当前边
                dis[ne.b] = Math.min(dis[ne.b], copyArray[ne.a] + ne.w);  // 更新到达ne.b点的最短距离
            }
        }
    }
}