最短路模型3:1100
作者:
总打瞌睡的天天啊
,
2024-10-20 16:52:56
,
所有人可见
,
阅读 2
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=200010;
int q[N];
int dist[N];
int main()
{
memset(dist,-1,sizeof dist);
int n,m;
cin>>n>>m;
int hh=0,tt=0;
q[0]=m;
dist[m]=0;
while(hh<=tt)
{
int t=q[hh++];
if(t+1==n)
{
cout<<dist[t]+1;
return 0;
}
if(t-1==n)
{
cout<<dist[t]+1;
return 0;
}
if(t%2==0&&t/2==n)
{
cout<<dist[t]+1;
return 0;
}
if(t-1>0&&dist[t-1]==-1)q[++tt]=t-1,dist[t-1]=dist[t]+1;
if(dist[t+1]==-1)q[++tt]=t+1,dist[t+1]=dist[t]+1;
if(t%2==0&&dist[t/2]==-1)q[++tt]=t/2,dist[t/2]=dist[t]+1;
}
}