# 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]);
}
}
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
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