AcWing 854. Floyd求最短路
原题链接
简单
作者:
半透明の微笑
,
2024-04-23 17:32:53
,
所有人可见
,
阅读 5
import java.io.*;
import java.util.*;
public class Main{
static int n, m, k;
static int N = 210;
static int[][] g = new int[N][N];
static int INF = 0x3f3f3f3f;
static void floyd(){
for(int k = 1; k <= n; k ++){
for(int i = 1; i <= n; i ++){
for(int j = 1; j <= n; j ++){
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
}
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 < N; i ++){
Arrays.fill(g[i], INF);
g[i][i] = 0;
}
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]);
g[x][y] = Math.min(g[x][y], z);
}
floyd();
for(int i = 0; i < k; i ++){
String[] s3 = br.readLine().split(" ");
int x = Integer.parseInt(s3[0]);
int y = Integer.parseInt(s3[1]);
if(g[x][y] > INF / 2 ) System.out.println("impossible");
else System.out.println(g[x][y]);
}
}
}