AT_abc429_e

· · 题解

思路

显然，答案为离每个 D 点的距离最近和次近的点的长度和。

显然是多元广搜。

对于每一个点，最有策略每个点一定入队正好两次。

然后统计次数即可。

需要注意距离不同不代表编号不同，S 点的首次入队也要记录。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=3000005;
typedef long long ll;
struct T
{
    int ne,to;
}e[2*N];
int he[N],idx,fi[N],se[N],vis[N],q[N],fii[N],f[N],id[N];
char a[N];
void add(int x,int y)
{
    e[++idx].ne=he[x];
    e[idx].to=y;
    he[x]=idx;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    int l=1,r=0;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(a[i]=='S')
        {
            q[++r]=i;
            id[r]=i;
            vis[i]=1;
            fii[i]=i;
        }
    }
    int cnt=0;
    while(r>=l)
    {
        int len=r-l+1;
        cnt++;
        while(len--)
        {
            int x=q[l],p=id[l];l++;
            for(int i=he[x];i;i=e[i].ne)
            {
                int y=e[i].to;
                if(vis[y]>=2)continue;
                if(vis[y]==1&&fii[y]==p)continue;
                vis[y]++;
                if(vis[y]==1)fi[y]=cnt,fii[y]=p;
                else se[y]=cnt;
                q[++r]=y;id[r]=p;
            }
        }
    }
    for(int i=1;i<=n;i++)
        if((!fi[i]||!se[i])&&a[i]!='S')while(1);
    for(int i=1;i<=n;i++)
        if(a[i]!='S')cout<<fi[i]+se[i]<<'\n';
    return 0;
}