c++实现flod算法

Floyd算法是一种用于求解带权图最短路径的算法，它是由Robert W. Floyd提出的，因此被命名为Floyd算法。C++实现Floyd算法的步骤如下：

1.定义二维数组dist表示两点之间的最短距离，初始化为图中两点之间的距离，若不存在则为无穷大。

2.三重循环，依次枚举所有点对之间的距离，通过比较中转点与起点、终点之间的距离和起点、终点之间的距离，更新dist数组。

3.输出dist数组即可。

下面是C++代码实现：

#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 205;

int n, m, q;
int dist[maxn][maxn];

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

int main() {
    cin >> n >> m >> q;
    // 初始化距离数组
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = INF;
            }
        }
    }
    // 输入边权
    for(int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dist[u][v] = min(dist[u][v], w);
        dist[v][u] = min(dist[v][u], w);
    }
    floyd();
    // 查询
    for(int i = 1; i <= q; i++) {
        int u, v;
        cin >> u >> v;
        if(dist[u][v] == INF) {
            cout << "-1\n";
        } else {
            cout << dist[u][v] << "\n";
        }
    }
    return 0;
}