| ||||||||||
| 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 | |||||||||
用spfa()过哦 230ms#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 551000
#define M 3001000
#define qm 1050000
struct arr{
int ff,ww,next,tt;
}c[M];
int d[N];
int q[qm + 15];
int k,n;
int tot;
int r[M];
bool v[N];
inline void add(int x,int y){
c[++tot].ff = x;
c[tot].tt = y;
c[tot].ww = 1;
c[tot].next = r[x];
r[x] = tot;
return;
}
int bfs(int s){
memset(d,0x3f,sizeof(d));
int h = 0, t = 0;
v[s] = 1;
d[s] = 0;
q[++t] = s;
while (h != t){
h = (h % qm) + 1;
int x = q[h];
v[x] = 0;
for (int i = r[x]; i ; i = c[i].next){
int y = c[i].tt;
if (d[y] > d[x] + c[i].ww){
d[y] = d[x] + c[i].ww;
if (!v[y]){
v[y] = 1;
t = (t % qm) + 1;
q[t] = y;
}
}
}
}
return d[k];
}
int main(){
#ifndef ONLINE_JUDGE
freopen("3278.in","r",stdin);
freopen("3278.out","w",stdout);
#endif
scanf("%d%d",&n,&k);
for (int i = 0; i <= 200000; i++){
add(i,i - 1);
add(i,i + 1);
add(i,i << 1);
}
printf("%d\n",bfs(n));
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator