影流之主已经被通知了一个逃脱的凛冬之怒的位置，并想立刻抓住她。他开始在一个点N（0≤N≤100000）一号线和凛冬之怒是在点K（0≤K≤100000）在同一号线。影流之主两种运输方式：幽灵疾步和传送。
*幽灵疾步：劫可以从任何点x点x 1 x + 1在一分钟
*传送：劫可以从任何点x在一分钟2点×X。
如果凛冬之怒不知道它的追求，根本不动，它需要多长时间来为影流之主进行检索呢？
输入
1号线：2个空格隔开的整数：N和K
输出
1号线：最少的时间，在几分钟内，它需要影流之主捕捉没闪现的凛冬之怒。
样本输入
17 5
样本输出
4
提示
影流之主劫到达凛冬之怒的最快方法是沿着以下路径：5-10-9-18-17移动，这需要4分钟。
3 条评论
-
hjp_handsome LV 8 @ 2015-10-29 16:24:42
转化为最短路问题，直接SPFA
-
@ 2015-07-01 14:20:53
这是poj题目P3278······
-
@ 2015-06-30 11:29:22
#include<iostream>
#include<cstring>
#include <cstdio>
#include <queue>
#define MAX 100005
using namespace std;queue<int> q;//jiewenqian //
int step[MAX];
bool visit[MAX];
int n,k;
int next,head;int bfs()
{
q.push(n);
step[n]=0;
visit[n]=1;
while(!q.empty())
{
head=q.front();
q.pop();
for(int i=0; i<3 ;i++)
{
if(i==0) next=head-1;
else if(i==1) next=head+1;
else next=head*2;
if(next>MAX || next<0 ) continue;
if(!visit[next])
{
q.push(next);
step[next]=step[head]+1;
visit[next]=1;
}
if(next==k) return step[next];
}
}
return -1;
}int main()
{
memset(visit,0,sizeof(visit));
scanf("%ld%ld",&n,&k);
printf("%d",bfs());
return 0;
}
- 1
