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

思路

由于处于同一个组的节点之间可以瞬移，所以这道题可以简化为当两个节点不处于同一个组时求两个组之间的最短距离，如果是同一个组就直接输入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;
}