题解：P11591 [NordicOI 2024] Anime Shops

· · 题解

以下将有动漫商店的点记为关键点，其它点记为非关键点。

这题看起来显然需要用到 bfs。但是因为求 n 次会寄，所以考虑只做一次，以所有关键点作为起点。

然后直接搜，搜到哪个非关键点就能直接知道非关键点的答案了。所以重点在于关键点的答案。

这里，我设当前有一个点 y，记录第一个搜到这个位置的关键点 a_y，也就是说离 y 最近的关键点之一（可以为自身）是 a_y。当与 y 相邻的另一个点 x 将要搜到 y 时，就可以更新 a_x 和 a_y 这两个点的答案，当前的距离为 a_x 到 x 的距离加上 a_y 到 y 的距离再 +1。

形象地说，整个 bfs 的过程像是 k 个关键点开始，每次向外扩展“领地”，比如 x 就被上面所说的 a_x 占领。当一个关键点将要扩展的“领地”已经被另一个关键点占领，就可以根据这两个关键点到该“领地”的距离算出这两个关键点之间的距离。

时间复杂度显然为 O(n+m)，因为每一次都恰好有一个非关键点被占领，并且每个非关键点最多被占领一次。

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
using namespace std;
int n,m,k,id[100010],a[100010],cnt[100010],ans[100010];
vector<int>v[100010];
void bfs()
{
    memset(ans,999999,sizeof(ans));
    queue<int>q;
    for(int i=1;i<=k;i++)
    {
        a[id[i]]=id[i];
        q.push(id[i]);
    }
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(auto y:v[x])
            if(a[y])
            {
                if(a[y]==a[x])continue;
                ans[a[y]]=min(ans[a[y]],cnt[y]+cnt[x]+1);
                ans[a[x]]=min(ans[a[x]],cnt[x]+cnt[y]+1);
            }
            else
            {
                a[y]=a[x],ans[y]=cnt[y]=cnt[x]+1;
                q.push(y);
            }
    }
}
int main()
{
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++)cin>>id[i];
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    bfs();
    for(int i=1;i<=n;i++)
        if(ans[i]<=1e9)cout<<ans[i]<<" ";
        else cout<<-1<<" ";
    cout<<endl;
    return 0;
}