Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用spfa()过哦 230ms

Posted by hzoi_hexing at 2014-02-24 14:51:16 on Problem 3278
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator