acwing-853. 有边数限制的最短路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.util.*;
class Main{
    static int N = 10010;
    //存放图数据
    static Node[] node = new Node[N];
    //定义距离
    static int[] dist = new int[N];
    static int inf = 1000000000;
    
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int k = sc.nextInt();
        
        for(int i = 1; i <= m; i++){
            int a = sc.nextInt();
            int b = sc.nextInt();
            int c = sc.nextInt();
            node[i] = new Node(a, b, c);
        }
        
        int result = bellmanFord(node, n, m, k);
        if(result == -1){
            System.out.print("impossible");
        }else{
            System.out.print(result);
        }
    }
    
    
    public static int bellmanFord(Node[] node, int n, int m, int k){
        //初始化距离
        Arrays.fill(dist, inf);
        dist[1] = 0;
        for(int i = 1; i <= k; i++){
            // copy距离
            int[] d = Arrays.copyOf(dist, N);
            
            // 遍历每一条边进行松弛
            for(int j = 1; j <= m; j++){
                int a = node[j].a;
                int b = node[j].b;
                int c = node[j].c;
                dist[b] = Math.min(dist[b], d[a] + c);
            }
        }
        
        return dist[n] > inf/2 ? -1 : dist[n];
    } 
}

//bellman-ford算法使用一个结果存储图
class Node{
    public int a;
    public int b;
    public int c;
    public Node(int a, int b, int c){
        this.a = a;
        this.b = b;
        this.c = c;
    }
}