2009-3-5pku1201.txt

数据结构中的单元最短路径算法的题目和源代码！其中所有的题目都能在PKU上找的到！

#include<stdio.h>
#include<string.h>
const int MAX=50005;
typedef struct Edge
{
	int next;
	int ed;
	int distance;
}Edge;
Edge edge[3*MAX];
int E,V;
int p[MAX];//在建设临接表的时候很有用
int d[MAX];//d[U]用来描述从源点S到U的最短路径上权值的上界
int q[MAX];//用来表示这个节点是不是已经使用了！
/*Bellman_Ford+队列优化*/
void Bellman_Ford(int S)
{ 
	int top=0; 
	bool use[MAX];
	memset(use,false,sizeof(use));
	memset(d,-1,sizeof(d));  
	int i,now;
	q[++top]=S;
	d[S]=0;
	use[S]=true; 
	while(top) 
	{
		now=q[top--]; 
		use[now]=false; 
		i=p[now]; 
		while(i!=-1) 
		{
			if(d[edge[i].ed]<d[now]+edge[i].distance)
			{
				d[edge[i].ed]=d[now]+edge[i].distance; 
				if(!use[edge[i].ed]) 
				{ 
					use[edge[i].ed]=true;     
					q[++top]=edge[i].ed; 
				}
			}  
			i=edge[i].next; 
		}
	} 
}
int main()
{
	int st,ed,distance,n,i;
	while(scanf("%d",&n)!=EOF)
	{
		E=V=0;
		memset(p,-1,sizeof(p));
		while(n--)
		{
			scanf("%d%d%d",&st,&ed,&distance);
			if(V<ed)V=ed;
			edge[E].ed=ed+1;
			edge[E].distance=distance;
			edge[E].next=p[st];
			p[st]=E++;
		}
		V++;
		for(i=1;i<=V;i++)
		{
			edge[E].ed=i;
			edge[E].distance=0;
			edge[E].next=p[i-1];
			p[i-1]=E++;
			edge[E].ed=i-1;
			edge[E].distance=-1;
			edge[E].next=p[i];
			p[i]=E++;
		}
		Bellman_Ford(0);
		printf("%d\n",d[V]);
	}
	return 0;
}
/*
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1


6
*/