题目描述
floyd 模板题打卡
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
JAVA 代码
import java.util.*;
import java.lang.*;
class Main{
/**
* 边数和点的的平方一个级别的 用邻接矩阵存储
*/
static int N = 210;
static int INF = 0x3f3f3f3f;
static int [][]g;
static void init(int n, int m){
g = new int[N][N];
//初始化图排掉重边和自环
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i!=j)g[i][j] = INF;
else g[i][j] = 0;
}
}
while(m-->0) {
int i = sc.nextInt(), j = sc.nextInt();
g[i][j] = Math.min(g[i][j],sc.nextInt());
}
}
static void floyd(int n, int m){
init(n,m);
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]);
}
}
}
}
static void printG(int n){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
System.out.print(g[i][j]+" ");
}
System.out.println();
}
}
static void floydAndQuery(int n, int m, int q){
floyd(n,m);
while(q-->0){
int a = sc.nextInt(),b = sc.nextInt();
int INF_2 = INF >> 1;
if(g[a][b] > INF_2) System.out.println("impossible");
else System.out.println(g[a][b]);
}
}
static Scanner sc = new Scanner(System.in);
public static void main(String []args){
floydAndQuery(sc.nextInt(),sc.nextInt(),sc.nextInt());
}
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla