13549

해결 방법

우선순위 큐를 이용하여 BFS 하듯이 돌면 된다.

조심할 점은 순간이동을 할때는 방문만 확인하는 것이 아니라 값도 비교해봐야한다.

#include <iostream> 

#include <iterator>

#include <algorithm> 

#include <vector>

#include <list>

#include <map>

#include <set>

#include <queue>

#include <stack>

#include <string>

#include <cmath>

#include <cstdio>

#include <cstring>

using namespace std;

#define MOD 1000000007

#define INF 2147483647

#define LNF 9223372036854775807

#define pb push_back

#define mp make_pair

typedef long long ll;

typedef unsigned long long ull;

typedef pair<ll,ll> pll;

typedef pair<int,int> pii;

int n,k,visit[100010];

int main (){

freopen("sample.txt","r",stdin);

scanf("%d%d",&n,&k);

memset(visit,-1,sizeof(visit));

priority_queue<pii, vector<pii>, greater<pii> > que;

que.push(mp(0,n));

visit[n]=0;

while(!que.empty()){

int c=que.top().first, u=que.top().second;

que.pop();

if(u+1<=100000 && visit[u+1]==-1){

que.push(mp(c+1,u+1));

visit[u+1] = c+1;

}

if(u-1>=0 && visit[u-1]==-1){

que.push(mp(c+1,u-1));

visit[u-1] = c+1;

}

if(2*u<=100000 && (visit[2*u]==-1 || visit[2*u]>c)){

que.push(mp(c,2*u));

visit[2*u] = c;

}

}

printf("%d\n",visit[k]);

return 0;

}