蓝桥杯备战 每日一题 (2)

发布时间:2024年01月19日

在这里插入图片描述
今天的题目是回忆迷宫

在这里插入图片描述

这个题目我们来熟悉一下 弗洛伊德算法 的代码模板
弗洛伊德算法用来处理最短路径问题

弗洛伊德算法(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);

这个要避免有重边

文章来源:https://blog.csdn.net/wniuniu_/article/details/135677876
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。