AcWing 854. Floyd求最短路

多源汇最短路,一般直接用Floyd算,时间复杂度为 $ O(n^3) $,然后存边的时候直接用邻接矩阵

在跑完Floyd之后,邻接矩阵d[x][y]里的数据就变成了$ 从x到y的最短距离了 $

当然,在初始化的时候,就把d[i][i],即自己到自己的距离,初始化成了0

Floyd算是最简单的最短路算法了,用到了动态规划的思想

唯一要注意的点就是,最外层循环的是$ k $,然后内部两层才是$ i和j $

之前有同学问可不可以用dijkstra或者别的单源最短路算法跑$ n $次,其实也是可以的

但是朴素dijkstra就是$ O(n^2) $的复杂度了,跑n次就到达了$ O(n^3) $

同样的复杂度,Floyd的代码还是短而且好写很多的

头文件里的#include <cstring>是多余的

因为这里是手动初始化的,没有用到memset(),同学们可以少写一行

题解源码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;    // n个点, m条边, Q个询问
int d[N][N];    // 邻接矩阵

// 注意内外层循环的顺序
void floyd(){
    for(int k = 1; k <= n; k ++)    // 最外层循环是k
        for(int i = 1; i <= n; i ++)    // 然后是i
            for(int j = 1; j <= n ; j ++)   // j
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);  // 这里很像动态规划的递推式
}

int main(){
    scanf("%d%d%d", &n, &m, &Q);

    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;

    for(int i = 0; i < m; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    for(int i = 0; i < Q; i ++ ){
        int a, b;
        scanf("%d%d", &a, &b);
        int t = d[a][b];
        if(t > INF / 2) puts("impossible");
        else printf("%d\n", t);
    }

    return 0;
}