3、Bellman-Ford最短路径

AcWing 853. 有边数限制的最短路

import java.util.*;
import java.util.concurrent.LinkedTransferQueue;

//ACWing
public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.init();
    }

    class Edge {
        int a, b, w;

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

    int n, m, k;
    int N = 10010;
    Edge []edges=new Edge[N];
    int dist[]=new int[N];
    int copyup[]=new int[N];
    int EXCEED=100000010;

    void bellman_ford(){
        Arrays.fill(dist,EXCEED);
        dist[1]=0;
        for (int i = 0; i < k; i++) {
            copyup=Arrays.copyOf(dist,dist.length);
            //copyup代表上一步没有执行的dist
            for (int j = 0; j < m; j++) {
                Edge e=edges[j];
                //仅仅通过当前点进行更新，不会发生任何串连
                if(dist[e.b]>copyup[e.a]+e.w){
                    dist[e.b]=copyup[e.a]+e.w;
                }
            }
        }
    }
    void init() {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        k = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            int a= scanner.nextInt();
            int b= scanner.nextInt();
            int w= scanner.nextInt();
            edges[i]=new Edge(a,b,w);
        }
        bellman_ford();
        if(dist[n]>EXCEED/2) System.out.println("impossible");
        else System.out.println(dist[n]);
    }
}