蓝桥杯2024年第十五届省赛真题-狡兔 k 窟

解题思路:因为ci相同的点距离为0，所以我们可以将ci相同的点看成一个点且可以用ci去表示这个点,然后跑一遍bfs就可以得到单源最短路径了(为什么?,因为距离都是1）ps:不知道为什么用Dijkstra会错4个点,求大佬告知
注意事项:

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int to;
	int next;
}mp[50050];
int head[50005];
int cnt=0;
queue<int>q;
int vis[5005],c[5005];
int dis[5005][5005];
void add(int u,int v) 
{
	mp[++cnt].next=head[u];
	mp[cnt].to=v;
	head[u]=cnt;
}
void bfs(int x,int y)
{
	q.push(x);
	dis[x][x]=0;
	vis[x]=1;
	while(!q.empty())
	{
		int u;
		u=q.front();
		q.pop();	
		for(int i=head[u];i;i=mp[i].next)
		{
			int v;
			v=mp[i].to;
			if(!vis[v])
			{
				dis[x][v]=dis[x][u]+1;
				q.push(v);
				vis[v]=1;
			}
		}
	}
}
int main()
{
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int x;
		scanf("%d",&c[i]);
	}
	for(int i=1;i<n;i++)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		add(c[x],c[y]);
		add(c[y],c[x]);
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			dis[i][j]=1E9+7;
		}	
	}
	while(m--)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(dis[c[x]][c[y]]!=1E9+7)//已经跑过bfs得出单源最短路径的就不用再跑一遍了
		{
			printf("%d\n",dis[c[x]][c[y]]);
		}
		else if(dis[c[y]][c[x]]!=1E9+7)
		{
			printf("%d\n",dis[c[y]][c[x]]);
		}
		else
		{
			memset(vis,0,sizeof(vis));
			bfs(c[x],c[y]);
			printf("%d\n",dis[c[x]][c[y]]);			
		}
	}
	return 0;
}