题目描述

一切都在代码中...

Java代码

/*
 如果存在负权回路，可能到某个点没有最短路径。如果这个负环在到题目中求的两个点的路径上，就一定没有最短路。
 但是，如果限制了路径经过的边数，负环就没有关系了，就一定存在最短路。

 时间复杂度：O(nm)
 1. 初始化dist[1]=0; dist[其他点] = 正无穷
 2. 循环n次         意义：迭代k次，dist数组代表从1号点经过不超过k条边，到每个点的最短距离
    1. 遍历所有边(a, b, w)，更新dist[b] = min(dist[b], dist[a] + w[b])。 ===> 松弛操作

 更新完后，dist[b] <= dist[a] + w[b]

 第一步的循环n次的含义：
    迭代k次，dist数组代表从1号点经过不超过k条边，到每个点的最短距离
    如果第n次迭代，dist数组还发生了改变，就代表从1号点存在一个最短路径上面有n条边，就代表路径上一定存在环，
    而且这环一定是负环
*/
import java.util.*;

public class Main {
    static int N = 510, M = 10010;
    static int n, m, k;
    // 代表图中边的集合
    static Edge[] edges = new Edge[M];
    // dist数组：代表当前1号点到i号点的最短距离
    // last数组：是dist数组的上一个状态的备份
    static int[] dist = new int[N], last = new int[N];
    // 代表无穷大
    static int INF = 0x3f3f3f3f;

    static int bellman_ford() {
        // 初始化
        for(int i = 0; i < N; i ++) dist[i] = INF; // Arrays.fill(dist, INF); 可以用这个就行初始化

        // 如果求i号点，到其他点的最短路，这里就初始化dist[i] = 0
        dist[1] = 0;
        // 由于这道题要求不超过k条边，所以这里最多遍历k次
        for(int i = 0; i < k; i ++) {

            // last[]数组是上一次迭代后dist[]数组的备份，由于是每个点同时向外出发，
            // 因此需要对dist[]数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点
            last = Arrays.copyOf(dist, N);

            // 遍历所有的边，更新每个点到1号点的距离
            for(int j = 0; j < m; j ++) {
                // 取出 a 到 b这一条边
                int a = edges[j].a, b = edges[j].b, w = edges[j].w;
                /* 这里用last数组，因为dist[a]在这一次 <= i条边的时候在更新dist[b]之前被更新了，
                 * 就会影响dist[b]的正确状态，然后dist[a] + w刚好又是最小的，就会错误，原因：原本这次是第i次更新，
                 * 而现在会导致到达 dist[b]这个点是 不超过i+1边的最小值，与本次更新是 <= i次矛盾
                 */
                dist[b] = Math.min(dist[b], last[a] + w);
            }
        }
        /* 在下面代码中，是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，而并非是if(dist[n] == INF)判断，
         * 原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可
         * 
         * 比如有一个节点a和n节点相连，a与其他节点距离为INF，所以会被在遍历所有边时更新，
         * 所以不一定等于INF
         */
        if (dist[n] > INF / 2) return -1;

        else return dist[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(), w = sc.nextInt();
            // 初始化所有的边
            edges[i] = new Edge(a, b, w);
        }

        int t = bellman_ford();
        if(t == - 1) System.out.println("impossible");
        else System.out.println(t);
    }


}
class Edge {
    // a 到 b的边的权值为 w
    int a, b, w;
    public Edge(int a, int b, int w) {
        this.a = a;
        this.b = b;
        this.w = w;
    }
}