多源最短路 c++ floyd 模板

好的，下面是多源最短路的 C++ Floyd 模板：

#include <bits/stdc++.h>
using namespace std;
const int N = 205;
const int INF = 0x3f3f3f3f;

int n, m;
int dis[N][N];

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
            }
        }
    }
}

int main() {
    cin >> n >> m;
    memset(dis, INF, sizeof(dis));
    for (int i = 1; i <= n; i++) dis[i][i] = 0;

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dis[u][v] = min(dis[u][v], w); // 处理重边
    }

    floyd();

    // 输出任意两点间的最短距离
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (dis[i][j] == INF) cout << "INF ";
            else cout << dis[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

其中，`dis[i][j]` 表示点 `i` 到点 `j` 的最短距离，初始化为无穷大。在读入边权的时候，如果出现重边，则取较小的一条边权。最后输出任意两点间的最短距离即可。