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丑陋代码!!!!

Posted by wocha at 2012-08-20 19:49:41 on Problem 1847
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <stack>
#include <queue>
#define inf 0x3f3f3f3f
#define M 110
#define ll __int64
using namespace std;
int end[M<<4],start[M<<4],next[M<<4],cost[M<<4],edge_num;
inline void Init(){
	edge_num=0;
	memset(start,-1,sizeof(start));
}
inline void add_edge (int u,int v ,int w){
	end[edge_num]=v;
	cost[edge_num]=w;
	next[edge_num]=start[u];
	start[u]=edge_num++;
}
bool visite[M];   int dist[M],cnt[M];
void spfa(int st,int n){
	memset(visite,false,sizeof(visite));
	memset(cnt,0,sizeof(cnt));
	memset(dist,inf,sizeof(dist));
	queue<int> my_queue;  int u,v,w;
	my_queue.push(st),visite[st]=true;
	cnt[st]++,dist[st]=0;
	while(!my_queue.empty()){
	  u=my_queue.front(),my_queue.pop(),visite[u]=false;
	  for(int i=start[u];i!=-1;i=next[i]){
  		v=end[i];  w=cost[i];
  		if(dist[v]>dist[u]+w){
		  	dist[v]=dist[u]+w;
		  	if(!visite[v]){
	  			visite[v]=true;
	  			my_queue.push(v);
	  			if(++cnt[v]>n)  return;
	  		}
		  }
  	}
	  	
	}
	return;
}
int main(){
    int n,start_position,end_position,k,edge;
	while(~scanf("%d%d%d",&n,&start_position,&end_position)){
            Init();
			for(int i=1;i<=n;i++){
			    scanf("%d",&k);
			for(int j=1;j<=k;j++){
				scanf("%d",&edge);
				if(j!=1)  add_edge(i,edge,1);
				else      add_edge(i,edge,0);
			}
		}
		spfa(start_position,n);
		if(dist[end_position]==inf) puts("-1");
		else   printf("%d\n",dist[end_position]);
	}	
	
	return 0;
}

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