双向广搜YYDS

双向广搜比普通BFS快了1900ms！！！

#include<bits/stdc++.h>
using namespace std;
const int N=5e7+5;
struct node{
	short x,step;
}vis[N];
struct r{
    int x;
    short step;
    bool is;
};
int t,n,a,b;
short bfs(){
	queue<r>q;
	q.push({a,0,1});
	q.push({b,0,0});
	vis[a]={1,0};
	vis[b]={2,0};
	while(!q.empty()){
		r fr=q.front();
		q.pop();
		int x1=fr.x-1,x2=fr.x+1,x3=fr.x<<1,x4=fr.x>>1;
        bool f=0;
        if(x4<<1==fr.x){
            f=1;
        }
        if(fr.is){
            if(x1>=0 && x1<n){
    			if(vis[x1].x==0){
    				vis[x1]={1,fr.step+1};
    				q.push({x1,fr.step+1,1});
    			}else if(vis[x1].x==2){
    				return fr.step+vis[x1].step;
    			}
    		}
    		if(x2>=0 && x2<n){
    			if(vis[x2].x==0){
    				vis[x2]={1,fr.step+1};
    				q.push({x2,fr.step+1,1});
    			}else if(vis[x2].x==2){
    				return fr.step+vis[x2].step;
    			}
    		}
            if(x3>=0 && x3<n){
    			if(vis[x3].x==0){
    				vis[x3]={1,fr.step+1};
    				q.push({x3,fr.step+1,1});
    			}else if(vis[x3].x==2){
    				return fr.step+vis[x3].step;
    			}
    		}
            if(x4>=0 && x4<n){
    			if(vis[x4].x==0){
    				vis[x4]={1,fr.step+1};
    				q.push({x4,fr.step+1,1});
    			}else if(vis[x4].x==2){
    				return fr.step+vis[x4].step;
    			}
    		}
        }else{
            if(x1>=0 && x1<n){
    			if(vis[x1].x==0){
    				vis[x1]={2,fr.step+1};
    				q.push({x1,fr.step+1,0});
    			}else if(vis[x1].x==1){
    				return fr.step+vis[x1].step;
    			}
    		}
    		if(x2>=0 && x2<n){
    			if(vis[x2].x==0){
    				vis[x2]={2,fr.step+1};
    				q.push({x2,fr.step+1,0});
    			}else if(vis[x2].x==1){
    				return fr.step+vis[x2].step;
    			}
    		}
    		if(x3>=0 && x3<n){
    			if(vis[x3].x==0){
    				vis[x3]={2,fr.step+1};
    				q.push({x3,fr.step+1,0});
    			}else if(vis[x3].x==1){
    				return fr.step+vis[x3].step;
    			}
    		}
            if(f && x4>=0 && x4<n){
    			if(vis[x4].x==0){
    				vis[x4]={2,fr.step+1};
    				q.push({x4,fr.step+1,0});
    			}else if(vis[x4].x==1){
    				return fr.step+vis[x4].step;
    			}
    		}
        }
	}
}
int main(){
	scanf("%d",&t);
	for(int i=1;i<=t;i++,putchar(10)){
        cin>>n>>a>>b;
        for(int i=0;i<n;i++){
        	vis[i]={0,0};
		}
		cout<<bfs()+1;
	}
    return 0;
}