AcWing 853. 有边数限制的最短路(Arrays.copyOf)
原题链接
简单
作者:
半透明の微笑
,
2024-04-23 16:42:40
,
所有人可见
,
阅读 4
import java.io.*;
import java.util.*;
public class Main{
static int n, m, k;
static int N = 510;
static int M = 100010;
static int[] dist = new int[N];
static int[] back = new int[N];
static PII[] edges = new PII[M];
static int INF = 0x3f3f3f3f;
static void bellman_ford(){
Arrays.fill(dist, INF);
dist[1] = 0;
for(int i = 0; i < k; i ++){
back = Arrays.copyOf(dist, n + 1);
for(int j = 0; j < m; j ++){
int x = edges[j].x;
int y = edges[j].y;
int z = edges[j].z;
dist[y] = Math.min(dist[y], back[x] + z);
}
}
if(dist[n] > INF / 2) System.out.println("impossible");
else System.out.println(dist[n]);
}
public static void main(String[] args)throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s1 = br.readLine().split(" ");
n = Integer.parseInt(s1[0]);
m = Integer.parseInt(s1[1]);
k = Integer.parseInt(s1[2]);
for(int i = 0; i < m; i ++){
String[] s2 = br.readLine().split(" ");
int x = Integer.parseInt(s2[0]);
int y = Integer.parseInt(s2[1]);
int z = Integer.parseInt(s2[2]);
edges[i] = new PII(x, y, z);
}
bellman_ford();
}
}
class PII{
int x;
int y;
int z;
public PII(int x, int y, int z){
this.x = x;
this.y = y;
this.z = z;
}
}