Advertisement
midnight_sun

Untitled

Nov 15th, 2022
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.84 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 1e9;
  4. int dist[MAXN];
  5. int n, k;
  6. int main(){
  7.     cin >> n >> k;
  8.     deque<int> dq;
  9.     dq.push_back(n);
  10.     memset(dist, 1e9, sizeof(dist));
  11.     dist[n] = 0;
  12.     while (dq.size()) {
  13.         int cur = dq.front();
  14.         dq.pop_front();
  15.         if (cur == k) {
  16.             cout << dist[k];
  17.             return;
  18.         }
  19.         int w = cur * 2;
  20.         if (w <= 200000 && dist[w] > dist[cur]) {
  21.             dist[w] = dist[cur];
  22.             dq.push_front(w);
  23.         }
  24.         int l = cur - 1, r = cur + 1;
  25.         if (l >= 0 && dist[l] > dist[cur] + 1) {
  26.             dq.push_back(l);
  27.             dist[l] = dist[cur] + 1;
  28.         }
  29.         if (r <= 200000 && dist[r] > dist[cur] + 1) {
  30.             dq.push_back(r);
  31.             dist[r] = dist[cur] + 1;
  32.         }
  33.     }
  34. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement