http://www.pipioj.online/problem.php?id=1024
1 #define IO std::ios::sync_with_stdio(0); 2 #define bug(x) cout<<#x<<" is "<<x<<endl 3 #include <bits/stdc++.h> 4 #define iter ::iterator 5 using namespace std; 6 typedef long long ll; 7 typedef pair<int,int>P; 8 #define pb push_back 9 #define mk make_pair 10 #define se second 11 #define fi first 12 #define rs o*2+1 13 #define ls o*2 14 const ll mod=1e9+7; 15 const int N=2e5+5,M=3e6; 16 17 int n,k; 18 19 int vis[N]; 20 21 struct node{ 22 int x,w; 23 bool operator <(const node &t)const{ 24 return w>t.w; 25 } 26 }; 27 28 int bfs(){ 29 node start; 30 start.x=n; 31 start.w=0; 32 priority_queue<node>q; 33 q.push(start); 34 for(int i=0;i<=k*2;i++){ 35 vis[i]=0; 36 } 37 vis[n]=1; 38 while(!q.empty()){ 39 node now=q.top(),ne; 40 q.pop(); 41 ne=now; 42 if(now.x==k)return now.w; 43 ne.w=now.w+1; 44 if(now.x<k){ 45 if(now.x>0){ 46 ne.x=now.x*2; 47 if(!vis[ne.x]){ 48 vis[ne.x]=1; 49 q.push(ne); 50 } 51 } 52 ne.x=now.x+1; 53 if(!vis[ne.x]){ 54 vis[ne.x]=1; 55 q.push(ne); 56 } 57 } 58 if(now.x>0){ 59 ne.x=now.x-1; 60 if(!vis[ne.x]){ 61 vis[ne.x]=1; 62 q.push(ne); 63 } 64 } 65 } 66 } 67 68 int main(){ 69 while(~scanf("%d%d",&n,&k)){ 70 if(n>=k){ 71 printf("%d ",n-k); 72 continue; 73 } 74 printf("%d ",bfs()); 75 } 76 77 }