今天的题目是回忆迷宫
这个题目我们来熟悉一下 弗洛伊德算法 的代码模板
弗洛伊德算法用来处理最短路径问题
弗洛伊德算法（Floyd’s algorithm）用于解决图中所有节点对之间的最短路径问题。算法的基本思路是通过逐步迭代更新节点对之间的最短路径长度，直到得到所有节点对之间的最短路径。
以下是弗洛伊德算法的大致思路：
初始化距离矩阵：创建一个二维矩阵，称为距离矩阵，用于存储节点对之间的最短路径长度。初始时，距离矩阵的值为图中节点之间的直接距离，如果两个节点之间没有直接边相连，则距离为无穷大。
迭代更新最短路径：通过遍历所有节点，对于每一对节点 (i, j)，检查是否存在一个中间节点 k，使得从节点 i 到节点 j 经过节点 k 的路径长度比直接从 i 到 j 的路径更短。如果存在这样的中间节点 k，则更新距离矩阵中节点 i 到节点 j 的最短路径长度为经过节点 k 的路径长度。
重复执行步骤 2：重复执行步骤 2，直到所有节点对之间的最短路径长度都被计算出来，即距离矩阵不再变化。
输出结果：输出距离矩阵，其中的每个元素表示对应节点对之间的最短路径长度。
弗洛伊德算法的核心思想是动态规划。通过逐步迭代更新节点对之间的最短路径长度，算法最终得到所有节点对之间的最短路径。由于需要遍历所有节点和中间节点，算法的时间复杂度为 O(n^3)，其中 n 是图中节点的数量。
总的来说就是，建模+核心的3个for循环
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]);
}
}
}
最终实现的代码如下
#include<iostream>
using namespace std;
typedef long long ll;
const int N = 410;
ll d[N][N]; // 开辟一个数组存储信息
int n, m, q; // 设置全局变量
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]);
}
}
}
}
int main()
{
cin >> n >> m >> q;
// 下面要进行初始化操作
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] = LLONG_MAX / 2;
}
}
while (m--)
{
ll a, b, c;
cin >> a >> b >> c;
d[a][b] = d[b][a] = min(d[a][b], c);
}
floyd();
while (q--)
{
int a, b;
cin >> a >> b;
if (d[a][b] >= LLONG_MAX / 2) cout << "-1" << endl;
else cout << d[a][b] << endl;
}
return 0;
}
有一个小细节，初始化数组的时候
d[a][b] = d[b][a] = min(d[a][b], c);
这个要避免有重边
