班班最大了

用户名：dotcpp0607166

访问量：7529

签　名：

哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

等　　级
排　　名	124
经　　验	7737
参赛次数	2
文章发表	35
年　　龄	3
在职情况	待业
学　　校	贺州学院
专　　业	数据

　　自我简介：

谢谢大家，让大家见笑了

TA的其他文章

C++简便易懂
浏览：91

区间合并（模板）（c++）
浏览：60

dfs模板题（排列数字）
浏览：52

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

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

　　作者: 班班最大了　　　　发表时间：2024-04-27 15:14:33 浏览：166　|　评论：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 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

班班最大了

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

上车人数（C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.8 （Java代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-整除问题（C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

大神老白（C语言代码）

一元一次方程（C语言代码）

1052题解（链表操作）

班班最大了

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

上车人数 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C++代码）（手动优化一下计算）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.8 （Java代码）

C语言训练-排序问题<1> （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

WU-整除问题 （C++代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

大神老白 （C语言代码）

一元一次方程 （C语言代码）

1052题解（链表操作）

上车人数（C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C++代码）（手动优化一下计算）

　　评论区

WU-整除问题（C++代码）

大神老白（C语言代码）

一元一次方程（C语言代码）