8-Floyd算法

算法思想

算法模板

import java.util.*;

public class Main {
    static int N = 210, M = 20010, INF = 0x3f3f3f3f;
    static int n, m, k;
    // d[i][j] 存储 i 号点到 j 号点的最短距离
    static int[][] d = new int[N][N];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        k = in.nextInt();
        
        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;
        
        while(m -- > 0)
        {
            int from = in.nextInt(), to = in.nextInt(), weight = in.nextInt();
            if(from == to) continue;
            d[from][to] = Math.min(d[from][to], weight);
        }
        
        floyd();
        
        while(k -- > 0)
        {
            int x = in.nextInt(), y = in.nextInt();
            var res = (d[x][y] > INF / 2) ? "impossible" : String.valueOf(d[x][y]);
            System.out.println(res);
        }
    }
	// d[k, i, j] 表示从 i 号点到 j 号点，只经过部分点集（1 ~ k 号点）的最短距离
	// d[k, i, j] = d[k - 1, i, k] + d[k - 1, k, j]
	// k, k-1 不参与运算，省略可得
	// d[i, j] = d[i, k] + d[k, j]
    static 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] = Math.min(d[i][j], d[i][k] + d[k][j]);
    }
}