1860E - Fast Travel Text Editor - CodeForces Solution

#include <bits/stdc++.h> 
#define mp make_pair
#define inf 0x3f3f3f3f
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define lowbit(i) (i&(-i))
//#define lx (x<<1)
//#define rx (x<<1|1)
//#define mid (left+right>>1)
using namespace std;
typedef long long ll;
const int N=5e4+5+26*26;
vector<pair<int,int>>e[N];
int d[N],a[N];
struct edge{
	int ans,x,y;
}b[N];
void dij(int i){
	d[i]=0;
	deque<int>q;
	q.push_front(i);
	while(!q.empty()){
		int x=q.front();q.pop_front();
		for(auto r:e[x]){
			int u=r.first,v=r.second;
			if(d[u]>d[x]+v){
				d[u]=d[x]+v;
				if(v){
					q.push_back(u);
				}else q.push_front(u);
			}
		}
	}
}
void solve(){
	string s;
	cin>>s;
	int n=s.length();
	for(int i=0;i<n;i++){
		if(i!=n-1){
			int j=n+(s[i]-'a')*26+s[i+1]-'a';
			e[j].push_back(mp(i,1));
			e[i].push_back(mp(j,0));
		}
		if(i!=n-1) e[i].push_back(mp(i+1,1));
		if(i!=0) e[i].push_back(mp(i-1,1));
	}
	int m;
	cin>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		x--;y--;
		b[i]=edge{abs(x-y),x,y};
	}
	for(int i=n;i<n+26*26;i++){
		memset(d,0x3f,sizeof(d));
		dij(i);
		for(int j=1;j<=m;j++){
			b[j].ans=min(b[j].ans,d[b[j].x]+d[b[j].y]-1);
		}
	}
	for(int  i=1;i<=m;i++){
		cout<<b[i].ans<<endl;
	}
}
int main(){
	IOS;
	int t;
	t=1;
	while(t--){
		solve();
	}
	return 0;
}