题目描述
Floyd求最短路
JAVA 代码
//解题思路:floyd算法的时间复杂度为O(n^3)
/*floyd算法使用了动态规划的思路,
g[i][j][k]表示从i走到j经过[1,k]的节点的路径的集合,
我们将这个集合按照路径包不包含第k个点划分为两个集合,
一个是g[i][j][k-1],
另一个是g[i][k][k-1]+g[k][j][k-1],
在这两者中取最小值,
我们发现当前这一层的状态只与上一层有关,所以可以省去一维。
*/
import java.util.*;
import java.io.*;
class Main{
static int N = 210;
static int[][] g = new int[N][N];
static int n,m,k;
static int max = 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][k] + g[k][j], g[i][j]);
}
}
}
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
k = sc.nextInt();
for(int i = 1; i<=n; i++){
for(int j=1; j<=n; j++){
if(i==j) g[i][j] = 0;
else g[i][j] = max;
}
}
for(int i =0; i<m; i++){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
g[a][b] = Math.min(c, g[a][b]);
}
floyd();
for(int i=0;i<k;i++){
int a = sc.nextInt();
int b = sc.nextInt();
if(g[a][b] >= max/2) System.out.println("impossible");
else System.out.println(g[a][b]);
}
}
}