求多源最短路 Floyd 算法模板

#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
int n, m;
int mp[105][104];
void floyd() {
    for(int k = 1; k <= n; k++) {
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(mp[i][j] > mp[i][k] + mp[k][j]) {
                    mp[i][j] = mp[i][k] + mp[k][j];
                }
            }
        }
    }

}
int main() {
    scanf("%d%d", &n, &m);
    memset(mp, inf, sizeof(mp));
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        mp[u][v] = w;
    }
    floyd();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
                if(i==j) continue;
            if(mp[i][j]!=inf) printf("顶点%d到顶点%d的距离为%d\n",i,j,mp[i][j]);
            else printf("顶点%d不能到达顶点%d\n",i,j);
        }
    }
    return 0;
}