自动搬运

查看原文

来自洛谷，原作者为

	Night_sea_64 距离省选还有 +inf 天。

搬运于2025-08-24 23:08:39，当前版本为作者最后更新于2025-01-18 19:57:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

这题看起来显然需要用到 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;
}