代码如下:
#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:队列爆了 估计 改成栈试试 (1724) crbtmac 2009-12-10 19:14:49
  • Re:队列爆了 估计 改成栈试试 (23) Rieman 2009-12-10 23:22:26