| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
Re:我靠,这题阴。注意是百万以上哈,小于百万就REIn Reply To:我靠,这题阴。注意是百万以上哈,小于百万就RE Posted by:dynamic_study at 2009-08-09 09:51:57 #include <iostream>
#include <queue>
#include <algorithm>
#define NIL 99999999
using namespace std;
const int N = 100000, K = 100005;
struct P
{
int p;
int step;
}Q[K];
int ANS;
bool inqueue[K];
int bfs(int n, int k)
{
int s = 0,e;
if(n == k)
return 0;
P now,next;
now.p = n;
now.step = 0;
Q[s] = now;
ANS = NIL;
e = s + 1;
inqueue[s] = true;
while(s < e)
{
now = Q[s++];
next = now;
next.p -= 1;
next.step++;
if(next.p == k)
{
ANS = min(ANS,next.step);
}
else
if(next.step < ANS && next.p >= 0 && next.p <= N && !inqueue[next.p])
Q[e++] = next,inqueue[next.p] = true;
next = now;
next.p += 1;
next.step++;
if(next.p == k)
{
ANS = min(ANS,next.step);
}
else
if(next.step < ANS && next.p >= 0 && next.p <= N && !inqueue[next.p])
Q[e++] = next,inqueue[next.p] = true;
next = now;
next.p *= 2;
next.step++;
if(next.p == k)
{
ANS = min(ANS,next.step);
}
else
if(next.step < ANS && next.p >= 0 && next.p <= N && !inqueue[next.p])
Q[e++] = next,inqueue[next.p] = true;
}
return ANS;
}
int main()
{
int n,k;
scanf("%d%d",&n,&k);
printf("%d\n",bfs(n,k));
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator