fork download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <queue>
  4. #include <string.h>
  5.  
  6. using namespace std;
  7.  
  8. struct item_t{
  9.     int u, w;
  10.  
  11.     item_t(){}
  12.     item_t(int uu, int ww){
  13.         u = uu, w = ww;
  14.     }
  15.  
  16.     bool operator< (const item_t& b) const{
  17.         return w > b.w;
  18.     }
  19. };
  20.  
  21. int cost[2000000];
  22. int disj(int src, int dest)
  23. {
  24.     priority_queue<item_t> que;
  25.     que.push(item_t(src, 0));
  26.     while(!que.empty()){
  27.         int u = que.top().u;
  28.         int w = que.top().w;
  29.         que.pop();
  30.         if(0 <= u && u <= 100000 && u == dest) return w;
  31.         if(0 <= u && u <= 100000 && (cost[u] == -1 || w < cost[u])){
  32.             cost[u] = w;
  33.             que.push(item_t(u - 1, w + 1));
  34.             que.push(item_t(u + 1, w + 1));
  35.             que.push(item_t(u * 2, w + 1));
  36.         }
  37.     }
  38.     return -1; // WA if I exclude this 
  39. }
  40.  
  41. int main()
  42. {
  43.     for(; ;){
  44.         memset(cost, -1, sizeof(cost));
  45.         int n, k;
  46.         if(!(cin >> n >> k)) break;
  47.         cout << disj(n, k) << "\n";
  48.     }
  49. }
  50.  
Success #stdin #stdout 0.01s 11280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/FdyTlU
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!