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

help!自己写的spfa+邻接表,为何RE?

Posted by Rieman at 2009-12-10 23:21:04 on Problem 3377
#include <iostream>
using namespace std;
const int maxx=(int)1e9,size=3000006;
int stack[size*10];
typedef struct list
{
  int value;       
  int weight;
  struct list *next;
}list;
list *head[size],*rear[size];
void initlist(int n)
{
  for(int i=1;i<n+1;i++)
  {
	head[i]=rear[i]=(list*)malloc(sizeof(list));
	head[i]->next=NULL;
	head[i]->weight=0;   
  }
}
void destroylist(int n)
{
  for(int i=1;i<n+1;i++)
	while(head[i])
	{
	  rear[i]=head[i]->next;
	  free(head[i]);
	  head[i]=rear[i];
	}
}
void enlistone(int a,int b,int c)
{
  list *p;
  p=(list*)malloc(sizeof(list));
  p->value=b;
  p->weight=c;
  p->next=NULL;
  rear[a]->next=p;
  rear[a]=p;
  head[a]->weight++;
}
void tralist(int a,int &h,int n,int *d,bool *in)  
{
  int b;
  int c;
  list *p;
  p=head[a]->next;
  while(p)
  {
	b=p->value;
	c=p->weight;
	if(d[a]+c<d[b])
	{
	  d[b]=d[a]+c;
	  if(!in[b])
	  {
		stack[++h]=b;
		in[b]=1;
	  }
	}
	p=p->next;
  }
}
void spfa(int vs,int n,int *shord)
{
  int h=1,x,k,i;
  bool ifin[size];
  for(i=1;i<n+1;i++)
  {
	stack[i]=ifin[i]=0;
	shord[i]=maxx;
  }
  shord[vs]=0;
  stack[h]=vs;
  ifin[vs]=1;
  while(h>0)
  {
	x=stack[h--];
	ifin[x]=0;
	tralist(x,h,n,shord,ifin);
  }
}
int main()
{
  int i,m,n,a,b,c,d;
  int x,shord[size];
  while(cin>>n&&n)
  {
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if(c)
	{
	  d=d+n+2;
	  b++;
	}
	else
	{
	  b=b+n+2;
	  d++;
	}
	initlist(2*n+2);
	for(i=1;i<n+1;i++)
	{
	  scanf("%d",&x);
	  enlistone(i,i+1,x);
	  enlistone(i+1,i,x);
	}
	for(i=1;i<n+2;i++)
	{
	  scanf("%d",&x);
	  enlistone(i,i+1+n,x);
	  enlistone(i+1+n,i,x);
	}
	for(i=n+2;i<2*n+2;i++)
	{
	  scanf("%d",&x);
	  enlistone(i,i+1,x);
	  enlistone(i+1,i,x);
	}
	spfa(d,2*n+2,shord);
	destroylist(2*n+2);
	printf("%d\n",shord[b]);
  }
  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