AcWing 853. 【Java】有边数限制的最短路
原题链接
简单
作者:
tt2767
,
2020-03-02 17:09:33
,
所有人可见
,
阅读 560
/*
1. bellmanFold算法: 扩展n-1 次, 代表存在一条经过n-1个边(n个点)的路径满足 dist[y] <= dist[x] + edge.v
2. 本题因为是扩展k次, 所以应该在扩展时使用 上一次的 dist值,反正本次之前的更新形成串联
3. 因为 +∞ 减去一个小值还是 +∞, 所以判断时候要 res[n-1] > INF >>1 , 防止 +∞被更新的情况
*/
import java.util.*;
public class Main{
class Edge{
int x, y, d;
public Edge(int x, int y, int d){
this.x = x;
this.y = y;
this.d = d;
}
}
static final int INF = Integer.MAX_VALUE >> 1;
void run(){
int n = jin.nextInt();
int m = jin.nextInt();
int k = jin.nextInt();
List<Edge> edges = new ArrayList<>();
for (int i = 0 ; i < m ; i++){
int x = jin.nextInt() - 1;
int y = jin.nextInt() - 1;
int d = jin.nextInt();
edges.add(new Edge(x, y, d));
}
int[] res = bellmanFord(edges, 0, n, k);
// String ans = res[n-1] == INF ? "impossible" : String.valueOf(res[n-1]);
String ans = res[n-1] > INF>>1 ? "impossible" : String.valueOf(res[n-1]);
System.out.println(ans);
}
public int[] bellmanFord(List<Edge> edges, int s, int n, int k){
int[] dis = new int[n];
int[] last = new int[n];
int m = edges.size();
Arrays.fill(dis, INF);
dis[s] = 0;
for (int i = 0 ; i < k ; i ++){
for (int j = 0 ; j < n ; j ++) last[j] = dis[j];
// for (int j = 0 ; j < n ; j ++) {
for (int j = 0 ; j < m ; j ++) {
Edge edge = edges.get(j);
dis[edge.y] = Math.min(dis[edge.y], last[edge.x] + edge.d);
}
}
return dis;
}
private Scanner jin = new Scanner(System.in);
public static void main(String[] args){new Main().run();}
}