#include<iostream>
using namespace std;
struct EDGE
{
	int a,b,c;
	EDGE *next;
}edge[150005];
EDGE *temp;
struct KID
{
	int candy;
	EDGE *first;
};
KID kid[30005];
int n,m,start=0,end;
int spfa()
{
	int stack[30005];
	int i,k,l,top=0;
	EDGE *record[30005];
	for(i=0;i<n;i++)
	{
		record[i]=kid[i].first;
	}
	bool visite[30005];
	memset(visite,false,sizeof(visite));
	kid[0].candy=0;
	stack[top++]=start;
	visite[start]=true;
	while(top>0)
	{
		k=stack[top-1];
		for(temp=record[k];temp!=NULL;temp=temp->next)
		{
			l=temp->b;
			if(kid[k].candy+temp->c<kid[l].candy)
			{
				kid[l].candy=kid[k].candy+temp->c;
				if(visite[l]==false)
				{
					visite[l]=true;
					stack[top++]=l;
					record[k]=temp;
					break;
				}
			}
		}
		if(temp==NULL)
		{
			visite[k]=false;
			top--;
		}
	}
	return kid[end].candy;
}
int main()
{
	int i,a,b,c;
	scanf("%d%d",&n,&m);
	end=n-1;
	for(i=0;i<n;i++)
	{
		kid[i].candy=INT_MAX;
		kid[i].first=NULL;
	}
	for(i=0;i<m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		a--;
		b--;
		edge[i].a=a;
		edge[i].b=b;
		edge[i].c=c;
		edge[i].next=kid[a].first;
		kid[a].first=&edge[i];
	}
	printf("%d\n",spfa());
	return 0;
}

• 解决了，md是spfa写错了，用了 (0) sige 2009-04-12 09:18:21
• 解决了，md是spfa写错了，用了4百多秒 (0) sige 2009-04-12 09:18:49
  • Re:解决了，md是spfa写错了，用了4百多秒 (5) 10074187 2009-05-10 21:54:27