Acwing Floyd算法

Floyd-Warshall 算法，用于解决图中任意两点之间的最短路径问题。Floyd-Warshall 是一种多源最短路径算法，可以处理带正权或负权的边，但要求图中不能有负权回路。

通过三层循环对每个顶点作为中转点 k 进行更新。通过检查是否通过节点 k 作为中转点可以找到更短的路径来更新最短距离
状态转移方程：d[i][j] = min(d[i][j], d[i][k] + d[k][j])，即从 i 到 j 的最短距离可以通过中转节点 k 更新。

初始化：

如果 i == j，即从节点 i 到节点 j 的距离为 0，因为它们是同一个节点；
如果 i != j，则初始时距离设置为无穷大 (INF)，表示两点之间没有直接路径。

板子：

 //初始化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;}}//d[a][b]表示a到b的最短距离
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]);}}}
}

Acwing 854.Floyd 求最短路

在这里插入图片描述

具体实现代码(详解版）：

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 210, INF = 1e9; // N为最大节点数，INF表示无穷大int n, m, Q;
int d[N][N]; // d[a][b] 表示 a 到 b 的最短距离// Floyd-Warshall 算法
void floyd() {// 通过每个节点 k 作为中转点，检查是否能找到更短的路径for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 更新从 i 到 j 的最短距离d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}
}int main() {cin >> n >> m >> Q;// 初始化 d 数组for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) d[i][j] = 0;  // 自己到自己的距离为 0else d[i][j] = INF;       // 其他点的初始距离为无穷大}}// 读取边信息，更新距离while (m--) {int a, b, w;cin >> a >> b >> w;d[a][b] = min(d[a][b], w);  // 避免重边，取最小值}// 运行 Floyd-Warshall 算法floyd();// 处理查询while (Q--) {int a, b;cin >> a >> b;// 如果 d[a][b] 大于无穷大的一半，表示无法到达if (d[a][b] > INF / 2) cout << "impossible" << endl;else cout << d[a][b] << endl;}return 0;
}