Floyd 全源最短路

CSP-J · 编程模板 · 片段 · cpp · 难度 3/5 · 共 768 字

插点法三重循环，适合 n 较小的情况

图论
全源最短路

前置内容

邻接表建图

正文

// Floyd：全源最短路
// 插点法，DP 思想
// 三重循环枚举中转点
// 适合 n 较小（n<=400）
#include <cstdio>
int d[405][405], n, m;
int main() {
    scanf("%d%d", &n, &m);
    // 初值：自环 0，其余无穷
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            d[i][j] = (i == j) ? 0 : 1e9;
    for (int i = 1; i <= m; i++) {
        int u, v, c;
        scanf("%d%d%d", &u, &v, &c);
        // 重边取较小者
        if (c < d[u][v]) d[u][v] = c;
    }
    // 枚举中转点 k
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                // 经 k 更短则松弛
                if (d[i][k] + d[k][j]
                    < d[i][j])
                    d[i][j] = d[i][k]
                        + d[k][j];
    printf("%d", d[1][n]);
    return 0;
}

Floyd 全源最短路

前置内容

正文

CSP-J · 编程模板的其它内容