题目链接

【题目描述】

农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点$N(0<=N<=100000)$，牛位于点$K(0<=K<=100000)$ 农夫有两种移动方式：

1、从 $X$ 移动到 $X-1$ 或 $X+1$ ，每次移动花费一分钟

2、从 $X$ 移动到 $2\ast X$ ，每次移动花费一分钟

假设牛没有意识到农夫的行动，站在原地不动。农夫最少要花多少时间才能抓住牛？

【思路】

最短路模型，直接建图跑dij会T，直接写BFS能过

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int maxn=200005;int n,s,t;int a[maxn];void bfs(){	queue
         
           que; que.push(s); a[s]=0; while(!que.empty()){ int x=que.front(); que.pop(); if(x==t) break; if(x-1>=0 && a[x-1]==-1){ a[x-1]=a[x]+1; que.push(x-1); } if(x+1<=n && a[x+1]==-1){ a[x+1]=a[x]+1; que.push(x+1); } if(x*2<=n && a[x*2]==-1){ a[x*2]=a[x]+1; que.push(x*2); } }}int main(){ scanf("%d%d",&s,&t); n=max(s,t)*2; memset(a,-1,sizeof(a)); bfs(); printf("%d\n",a[t]); return 0;}