Floyd求最短路

题目描述

给定一个 $ n $ 个点 $ m $ 条边的有向图，图中可能存在重边和自环，边权可能为负数。
再给定 $ k $ 个询问，每个询问包含两个整数 $ x $ 和 $ y $ ，表示查询从点 $ x $ 到点 $ y $ 的最短距离，如果路径不存在，则输出impossible。
数据保证图中不存在负权回路。
输入格式
第一行包含三个整数 $ n,m,k。 $
接下来 $m$ 行，每行包含三个整数 $x,y,z,$ 表示存在一条从点 $x$ 到点 $y$ 的有向边，边长为 $z$。
接下来 $k$ 行，每行包含两个整数 $x,y$，表示询问点 $x$ 到点 $y$ 的最短距离。
输出格式
共 $k$ 行，每行输出一个整数，表示询问的结果，若询问两点间不存在路径，则输出 impossible。
数据范围
$1\le n \le 200,1 k \le n2 , 1 \le m \le 20000$,图中涉及边长绝对值均不超过 $10000$。
输入样例：

3 3 2
1 2 1
2 3 2
1 3 1
2 1
1 3

输出样例:

impossible
1

$Floyd$算法（也称插点法），代码偏简单，与$dijkstra$算法类似,是基于动态规划思想的一个多源化最短路，时间复杂度为 $O({n ^3})$
状态转移方程:

f[k][i][j] = min(f[k][i][j],f[k - 1][i][k] + f[k - 1][k][j]);

去一维

f[i][j] = min(f[i][j],f[i][k] + f[k][j]);

$Floyd$优点：码量小，偏简单
$Floyd$缺点：时间复杂度高$O(n ^ 3)$

模板

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]);
}

代码

#include <iostream>
using namespace std;
const int N = 210, M = 2e+10, INF = 1e9;
int n, m, k, x, y, z;
int d[N][N];
void floyd() {//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]);//求最短，所以用min
}
int main() {
    cin >> n >> m >> k;
    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--) {
        cin >> x >> y >> z;
        d[x][y] = min(d[x][y], z);
        //注意保存最小的边
    }
    floyd();
    while (k--) {
        cin >> x >> y;
        if (d[x][y] > INF / 2) puts("impossible");
        //由于有负权边存在所以约大过INF/2也很合理
        else cout << d[x][y] << endl;
    }
    return 0;
}