专栏文章

题解：P12126 [蓝桥杯 2024 省 B 第二场] 狡兔 k 窟

BBill_luogu
P12126题解参与者 4已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@miovrfdt
此快照首次捕获于
2025/12/03 01:57
3 个月前
此快照最后确认于
2025/12/03 01:57
3 个月前
查看原文

题目思路：

用 BFS。（因为 Dijkstra 时间复杂度为 O(mnlog⁡n+m2)O(mn\log n+m^2)，会 TLE）

BFS 步骤

先把 csic_{s_{i}} 加入队列，再从 csic_{s_{i}} 开始 BFS，走过的点标记为 11。因为是 BFS，所以一旦搜到 ctic_{t_{i}} 即可输出答案（把 cuic_{u_{i}} 和 cvic_{v_{i}} 连双向边），时间复杂度 O(nm)O(nm)。
记得清空！！！

AC Code：

CPP
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
bool vis[5010];
struct node{
	int x,step;
};
queue<node> q;
vector<int> v[5010];
int n,m;
int c[5010];
//int ans;
void bfs(int st,int ed)
{
	memset(vis,0,sizeof vis);
	while(q.size())q.pop();
	q.push((node){st,0});
	while(q.size())
	{
		node now=q.front();
		q.pop();
		if(now.x==ed)
		{
			cout<<now.step<<'\n';//输出答案
			return;
		}
		if(vis[now.x])continue;
		vis[now.x]=1;
		for(int i=0;i<v[now.x].size();i++)
			q.push((node){v[now.x][i],now.step+1});
	}
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>c[i];
	for(int i=1,x,y;i<n;i++)
	{
		cin>>x>>y;
        //连边
		v[c[x]].push_back(c[y]);
		v[c[y]].push_back(c[x]);
	}
	while(m--)
	{
		int x,y;
		cin>>x>>y;
		bfs(c[x],c[y]);//开始 BFS
	}
	return 0;
}
然后我们就愉快的 AC 啦！

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...