AcWing 853. 有边数限制的最短路
原题链接
简单
作者:
FayunYm
,
2021-01-07 16:58:34
,
所有人可见
,
阅读 290
import java.io.*;
import java.util.Arrays;
public class Main {
static final int N = 510;
static int n, m, k;
static int[] dist;
static int[] backup; //备份上一次迭代后的距离
static Edge[] edge;
static final int DIST = 0x3f3f3f3f;
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] s = reader.readLine().split(" ");
n = Integer.parseInt(s[0]);
m = Integer.parseInt(s[1]);
k = Integer.parseInt(s[2]);
dist = new int[n+1];
Arrays.fill(dist, 1,n+1,DIST);
backup = new int[n+1];
edge = new Edge[m];
for(int i = 0; i < m; i++) { //对象数组别忘了实例化
s = reader.readLine().split(" ");
edge[i] = new Edge(Integer.parseInt(s[0]),Integer.parseInt(s[1]),Integer.parseInt(s[2]));
}
int t = bellmanFord();
if(t == -1) System.out.println("impossible");
else System.out.println(t);
reader.close();
}
private static int bellmanFord() {
dist[1] = 0;
for (int i = 0; i < k; i++) { //题目只要求迭代k次
backup = Arrays.copyOf(dist, m+1);
for (int j = 0; j< m; j++) { //每次迭代都更新距离
int a = edge[j].a;
int b = edge[j].b;
int w = edge[j].w;
dist[b] = Math.min(dist[b], backup[a] + w);
}
}
if (dist[n] > 0x3f3f3f3f / 2) return -1; //这里注意
return dist[n];
}
}
class Edge {
public int a;
public int b;
public int w;
public Edge(int a, int b, int w) {
this.a = a;
this.b = b;
this.w = w;
}
}