CF1860E

· · 题解

拿到这种题很难不往最短路上面去想，于是得出：

相邻两个连一条边权为 1 的边，对于每两个字母，建一个源点代表该情况，随后每个点往自己的情况连一条边权为 0.5 的边。但是浮点数有点难处理，所以将每条边边权乘 2，这样就可以 01bfs 了。

这样做完之后就遇到了一个问题，如何统计答案呢？m 组询问每次跑一遍最短路肯定是不可取的。注意到源点数量最多仅为 26 \times 26=676，我们枚举每个源点作为出发点，代表路径经过该源点进行一次跳跃，最后统计答案的时候除以 2 即可。

#include<bits/stdc++.h>
#define int long long
#define FastIO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define I using
#define AK namespace
#define CSPS2026 std
I AK CSPS2026;
const int maxn=1e6+10,maxm=8e4+10,maxqwq=700,mod=998244353,inf=1e9;
int t,n,m,x,y,z,u,v,w,ans,arr[maxn],vis[maxn],dis[maxqwq][maxm];
char s[maxn];
vector<pair<int,int> >e[maxn];
deque<int>q;
int calc(char c,char d)
{
    return (c-'a')*26+(d-'a');
}
void bfs(int s)
{
    for(int i=1;i<=m+x;i++)
    {
        dis[s][i]=inf;
        vis[i]=0;
    }
    q.push_front(s+m);
    dis[s][s+m]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop_front();
        if(vis[u])continue;
        vis[u]=1;
        for(auto v:e[u])
        {
            if(dis[s][v.first]>dis[s][u]+v.second)
            {
                dis[s][v.first]=dis[s][u]+v.second;
                if(vis[v.first])continue;
                if(!v.second)q.push_front(v.first);
                else q.push_back(v.first);
            }
        }
    }
    return;
}
signed main()
{
    FastIO;
    cin>>(s+1)>>n;
    m=(int)(strlen(s+1));
    x=26*26;
    for(int i=1;i<m;i++)
    {
        v=calc(s[i],s[i+1]);
        if(i!=1) e[i].push_back({i-1,2});
        if(i!=m-1) e[i].push_back({i+1,2});
        e[i].push_back({v+m,1});
        e[v+m].push_back({i,1});
    }
    for(int i=0;i<x;i++)bfs(i);
    for(int i=1;i<=n;i++)
    {
        cin>>u>>v;
        if(u>v)swap(u,v);
        ans=v-u;
        for(int i=0;i<x;i++)ans=min(ans,(dis[i][u]+dis[i][v])>>1);
        cout<<ans<<"\n";
    }
    return 0;
}