第十五届蓝桥杯C++B组第二场真题-狡兔k窟

402 阅读 0 评论 0 点赞

##思路
由于处于同一个组的节点之间可以瞬移，所以这道题可以简化为当两个节点不处于同一个组时求两个组之间的最短距离，如果是同一个组就直接输入0.
```
#include <bits/stdc++.h>
#define PII pair<int,int>
#define se second
#define fi first
using namespace std;
const int N = 5010;
int n,m;
int ji[N],lu[N];          //用来记录点是否被访问过,边是否被访问过 
int a[N],juli[N][N];      //组数，组与组的距离
vector<int> g[N];
vector<int> tu[N];
void bfs(vector<int> &o,int i){
	memset(ji,0,sizeof ji);
	memset(lu,0,sizeof lu);
	ji[i]=1;               //标记起始节点i为已访问.
	queue<PII> q;
	for(auto e:o){         //对于o中的每个节点e(o是与e相关的所有节点),将其标记为已访问的边，并将其与距离0(起始距离)一起加入队列.

lu[e]=1;
		q.push({e,0});
	}
	while(!q.empty()){     //当队列不为空时，取出队首的节点和距离，并从队列中移除.
		PII p=q.front();
		q.pop();
		for(auto f:tu[p.fi]){//对于当前节点p.fi的每一个邻居f,如果邻居的a[f]未被访问过(!ji[a[f]])且这条边未被访问过(!lu[f]),则标记该节点为已访问.
			if(!ji[a[f]] && !lu[f]){
				ji[a[f]]=1;
				for(auto j:g[a[f]]){//对于a[f]的所有节点j,标记边为已访问,并更新从i到a[j]的最短距离(如果新的距离更短).然后,将节点j与新的距离一起加入队列,以便进一步搜索.
					lu[j]=1;
					juli[i][a[j]]=min(juli[i][a[j]],p.se+1);
					q.push({j,p.se+1});
				}
			}
		}
	}
}
int main(){
	memset(juli,0x3f,sizeof juli);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		g[a[i]].push_back(i);
	}
	for(int i=1;i<n;i++){         //建立图
		int c,d;
		scanf("%d%d",&c,&d);
		tu[c].push_back(d);
		tu[d].push_back(c);
	}
	for(int i=1;i<N;i++){          //遍历一遍每个组
		if(g[i].size()) bfs(g[i],i);
	}
	while(m--){
		int c,d;
		scanf("%d%d",&c,&d);
		if(a[c]==a[d]) printf("0\n"); //如果是同一个组
		else printf("%d\n",juli[a[c]][a[d]]);
	}
	return 0;
}
```

0.0分

1 人评分

本文分类：文章列表
浏览次数：402 次浏览
发布日期：2024-04-27 15:14:33
本文链接：https://blog.dotcpp.com/a/104702

上一篇 > 第十五届蓝桥杯C++B组第二场真题-遗迹
下一篇 > 1023选择排序（C++）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

第十五届蓝桥杯C++B组第二场真题-狡兔k窟

评论列表共有 0 条评论

发表评论取消回复

第十五届蓝桥杯C++B组第二场真题-狡兔k窟

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复