> 代码如下:
> #include <iostream>
> using namespace std;
> const int maxx=(int)1e9,size=50000;
> 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 &r,int n,int *q,int *d,bool *in)  
> {
>   int b,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])
> 	  {
> 		q[++r]=b;
> 		in[b]=1;
> 	  }
> 	}
> 	p=p->next;
>   }
> }
> int spfa(int vs,int n,int *shord)
> {
>   int h=0,r=1,x,i,queue[size];
>   bool ifin[size];
>   for(i=1;i<n+1;i++)
>   {
> 	queue[i]=ifin[i]=0;
> 	shord[i]=maxx;
>   }
>   shord[vs]=0;
>   queue[r]=vs;
>   ifin[vs]=1;
>   while(h<r)
>   {
> 	x=queue[++h];
> 	ifin[x]=0;
> 	tralist(x,r,n,queue,shord,ifin);
>   }
>   return h;
> }
> int main()
> {
>   int i,m,n,a,b,c,shord[size];
>   while(cin>>n>>m)
>   {
> 	initlist(n);
> 	for(i=0;i<m;i++)
> 	{
> 	  scanf("%d%d%d",&a,&b,&c);
> 	  enlistone(a,b,c);
> 	}
> 	spfa(1,n,shord);
> 	cout<<shord[n]<<endl;	
>   }
>   return 0;
> }
>         

• Re:队列爆了 估计 改成栈试试 (23) Rieman 2009-12-10 23:22:26