floyd模板

初始化：
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            if (i == j) d[i][j] = 0;
            else d[i][j] = INF;

// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{
    for (int k = 1; k <= n; k ++ )
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= n; j ++ )
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}

例题：
4074. 铁路与公路

import java.util.*;
public class Main {
	static int INF = 0x3f3f3f3f;
	static int N = 405;
	static int n,m;
	
	static int floyd(int f[][]) {
		if(f[1][n] != INF) return f[1][n];
		
		for(int k = 1; k <= n; k ++ ) {
			for(int i = 1; i <= n; i ++ ) {
				for(int j = 1; j <= n; j ++ ) {
					f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j]);
				}
			}
		}
		return f[1][n];
	}
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int f[][] = new int [N][N];
    	int g[][] = new int [N][N];
        n = sc.nextInt();
        m = sc.nextInt();
        for(int[] t:f) Arrays.fill(t, INF);
        for(int[] t:g) Arrays.fill(t, INF);
        for(int i = 0; i < m; i ++ ) {
        	int a = sc.nextInt();
        	int b = sc.nextInt();
        	f[a][b] = 1;
        	f[b][a] = 1;
        }
        
        for(int i = 1; i <= n; i ++ ) {
        	for(int j = 1; j <= n; j ++ ) {
        		if(f[i][j] == INF && i != j) {
        			g[i][j] = 1;
        		}
        	}
        }
        int res = Math.max(floyd(f),floyd(g));
        if(res != INF)
            System.out.println(res);
        else
            System.out.println(-1);
        sc.close();
    }
}