Floyd求最短路

$floyd$概述

这是解决多元汇最短路的唯一方法，时间复杂度是$O(n ^ 3)$

求解思路

本题是动态规划的思路求解的，本来是三维，后面通过滚动数组降至二维

$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$放在最外层。

具体思路就是三重循环
第一重枚举的是阶段，是只经过第$1$到$k$个点的所有路径的最短距离
第二重枚举的是起点，第三重枚举的是终点
最内层，就是把第$k$个点当做中间过渡点能否降低距离的判断
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);

数据存储

整体采用邻接矩阵存储
重边选用最小边，自环去掉

初始化时候，自己到自己的距离设置为0，其余的边设置为不可达（正无穷）

可达性判断

由于边权可能为负数，而且多源汇会计算所有的边，无穷会被减去一些（它还是一个很大的数字），所以这里处理如$bellman$-$ford$算法，如果距离大于一个很大的数据则为不可达

代码

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

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d[N][N];

void floyd() // 三重循环，k, i, j
{
    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]);
}

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;

    while (m -- ) // 读入数据
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        d[a][b] = min(d[a][b], c);
    }

    floyd();

    while (Q -- )
    {
        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;
}