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

· · 题解

题目思路：

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

BFS 步骤

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

记得清空！！！

AC Code：

#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 啦！