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