算法分析

(y总真言，简单易懂)

• f[i, j, k]表示从i走到j的路径上除i和j点外只经过1到k的点的所有路径的最短距离。那么f[i, j, k] = min(f[i, j, k - 1), f[i, k, k - 1] + f[k, j, k - 1]。
  因此在计算第k层的f[i, j]的时候必须先将第k - 1层的所有状态计算出来，所以需要把k放在最外层。

• 读入邻接矩阵，将次通过动态规划装换成从i到j的最短距离矩阵

• 在下面代码中，判断从a到b是否是无穷大距离时，需要进行if(t > INF/2)判断，而并非是if(t == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，t大于某个与INF相同数量级的数即可

时间复杂度 $O(n^3)$

Java 代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {
    static int n;
    static int m;
    static int q;
    static int N = 210;
    static int INF = 0x3f3f3f3f;
    static int[][] d = new int[N][N];
    public 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]);
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] str1 = reader.readLine().split(" ");
        n = Integer.parseInt(str1[0]);
        m = Integer.parseInt(str1[1]);
        q = Integer.parseInt(str1[2]);
        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)
        {
            String[] str2 = reader.readLine().split(" ");
            int a = Integer.parseInt(str2[0]);
            int b = Integer.parseInt(str2[1]);
            int c = Integer.parseInt(str2[2]);
            d[a][b] = Math.min(d[a][b], c);//若有重边选择短的边
        }
        floyd();
        while(q -- > 0)
        {
            String[] str3 = reader.readLine().split(" ");
            int a = Integer.parseInt(str3[0]);
            int b = Integer.parseInt(str3[1]);
            int t = d[a][b];
            if(t > INF / 2) System.out.println("impossible");
            else System.out.println(t);

        }

    }

}