2009-2-20-pku1511.txt

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

一个SPFA()的算法！
！！！！！！！！！
#include<stdio.h>
#include<string.h>
const int MAX=1000005;
const int INF=0x7fffffff;
typedef struct Node
{   //邻接表
	int next;//边的开始点
	int to;//边的目的点
	int distance;//边的权值
}Node;
Node node[MAX];
Node node1[MAX];
int p[MAX];//在建设临接表的时候很有用
int p1[MAX];//同上
int d[MAX];//d[U]用来描述从源点S到U的最短路径上权值的上界
int q[MAX];//状态数组模拟队列！
bool use[MAX];//用来表示这个节点是不是已经使用了！
//short_path_faster_algorithm
//更快的最短路径算法
void SPFA(int V,int S)
{
	int i,j,front,rear,temp;
	for(i=1;i<=V;i++)
		d[i]=INF;
	d[S]=0;
	memset(use,false,sizeof(use));
	front=-1;
	rear=0;
	q[rear]=S;
	use[S]=true;
	while(front!=rear)
	{
		front=(front+1)%MAX;
		temp=q[front];
		for(j=p[temp];j!=-1;j=node[j].next)//只是对某个节点相邻节点使用松弛技术！
		{
			if(d[temp]<INF&&d[temp]+node[j].distance<d[node[j].to])
			{
				d[node[j].to]=d[temp]+node[j].distance;
				if(!use[node[j].to])
				{
					use[node[j].to]=true;
					rear=(rear+1)%MAX;
					q[rear]=node[j].to;
				}
			}
		}
		use[temp]=false;
	}
}
//
void SPFA1(int V,int S)
{
	int i,j,front,rear,temp;
	for(i=1;i<=V;i++)
		d[i]=INF;
	d[S]=0;
	memset(use,false,sizeof(use));
	front=-1;
	rear=0;
	q[rear]=S;
	use[S]=true;
	while(front!=rear)
	{
		front=(front+1)%MAX;
		temp=q[front];
		for(j=p1[temp];j!=-1;j=node1[j].next)
		{
			if(d[temp]<INF&&d[temp]+node1[j].distance<d[node1[j].to])
			{
				d[node1[j].to]=d[temp]+node1[j].distance;
				if(!use[node1[j].to])
				{
					use[node1[j].to]=true;
					rear=(rear+1)%MAX;
					q[rear]=node1[j].to;
				}
			}
		}
		use[temp]=false;
	}
}
int main()
{
	int T,V,E,i;
	int st,ed,distance;
	__int64 sum;
	scanf("%d",&T);
	while(T--)
	{
		sum=0;
		scanf("%d%d",&V,&E);
		memset(p,-1,sizeof(p));//初始化,别忘了!
		memset(p1,-1,sizeof(p1));
		for(i=0;i<E;i++)
		{//下面的输入就是构建邻接表！
		 //很值得学习并且记住！
			scanf("%d%d%d",&st,&ed,&distance);
			node[i].next=p[st];
			node[i].distance=distance;
			node[i].to=ed;
			p[st]=i;
                  //构建上图的反向邻接表！
			node1[i].next=p1[ed];
			node1[i].distance=distance;
			node1[i].to=st;
			p1[ed]=i;
		}
		SPFA(V,1);
		for(i=1;i<=V;i++)
			sum+=d[i];
		SPFA1(V,1);
		for(i=1;i<=V;i++)
			sum+=d[i];
		printf("%I64d\n",sum);
	}
	return 0;
}
第二个 
//上海交大的模板Bellman_Ford+Queue
//scr-表示源点  n-表示顶点的个数 m-表示边的个数
#include<stdio.h>
#include<string.h>
const int MAXV=1000015;
const int MAXE=1000015;
const int INF=1000000000;
typedef struct Edge
{
	int st;
	int ed;
	int distance;
}Edge;
Edge edge[MAXE];
int nbs[MAXV],next[MAXE],value[MAXV],open[MAXV],open1[MAXV];
int ev[MAXE],ew[MAXE],mk[MAXV],n,m,num,cur,tail;
//上海交大的模板Bellman_Ford+Queue
//scr-表示源点  n-表示顶点的个数 m-表示边的个数
void Bellman_Ford(int src)
{
	int i,t,u,v,p=0;
	for(i=1;i<=n;i++)
	{value[i]=INF;mk[i]=0;}
	value[src]=tail=0;open[0]=src;
	while(++p,tail>=0)
	{
		for(i=0;i<=tail;i++) open1[i]=open[i];
		for(cur=0,t=tail,tail=-1;cur<=t;cur++)
			for(u=open1[cur],i=nbs[u];i;i=next[i])
			{
				v=ev[i]; 
				if(value[u]+ew[i]<value[v])
				{
				   value[v]=value[u]+ew[i];
				   if(mk[v]!=p){open[++tail]=v;mk[v]=p;}
				}
			}
	}
	
}
int main()
{
	int i,u,v,w,T;
	__int64 sum;
	scanf("%d",&T);
	while(T--)
	{
		sum=num=0;
		scanf("%d%d",&n,&m);
		memset(nbs,0,sizeof(nbs));
		for(i=1;i<=m;i++)
		{
			scanf("%d%d%d",&u,&v,&w);
			edge[i].st=v;
			edge[i].ed=u;
			edge[i].distance=w;
			next[++num]=nbs[u];
			nbs[u]=num;
			ev[num]=v;
			ew[num]=w;
		}
		Bellman_Ford(1);
		for(i=1;i<=n;i++)
			sum+=value[i];
		num=0;
		memset(nbs,0,sizeof(nbs));
		for(i=1;i<=m;i++)
		{
			next[++num]=nbs[edge[i].st];
			nbs[edge[i].st]=num;
			ev[num]=edge[i].ed;
			ew[num]=edge[i].distance;
		}
		Bellman_Ford(1);
		for(i=1;i<=n;i++)			
			sum+=value[i];
		printf("%I64d\n",sum);
	}
	return 0;
}
/*
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50

46
210
*/
第三方法：
这个模板已经很不错了啊！
比前面的都快啊！
#include<stdio.h>
#include<string.h>
const int MAX=1000015;
const int INF=0x6fffffff;
typedef struct Edge
{
	int next;
	int ed;
	int distance;
}Edge;
Edge edge[MAX];
Edge edge1[MAX];
int p[MAX];//在建设临接表的时候很有用
int d[MAX];//d[U]用来描述从源点S到U的最短路径上权值的上界
int q[MAX];//用来表示这个节点是不是已经使用了！
/*Bellman_Ford+队列优化*/
void Bellman_Ford(int V,int S)
{ 
	int top=0; 
	bool use[MAX];
	int i,now;
	memset(use,false,sizeof(use));
	for(i=1;i<=V;i++)
		d[i]=INF;
	d[S]=0;
	q[++top]=S;
	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,T,i,V,E;
	__int64 sum;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&V,&E);
		memset(p,-1,sizeof(p));
		for(i=1;i<=E;i++)
		{
			scanf("%d%d%d",&st,&ed,&distance);
			edge1[i].next=ed,edge1[i].ed=st,edge1[i].distance=distance;
			edge[i].next=p[st];
			edge[i].ed=ed;
			edge[i].distance=distance;
			p[st]=i;
		}
		sum=0;
		Bellman_Ford(V,1);
		for(i=1;i<=V;i++)
			sum+=d[i];
		memset(p,-1,sizeof(p));
		for(i=1;i<=E;i++)
		{
			edge[i].next=p[edge1[i].next];
			edge[i].ed=edge1[i].ed;
			edge[i].distance=edge1[i].distance;
			p[edge1[i].next]=i;
		}
		Bellman_Ford(V,1);
		for(i=1;i<=V;i++)
			sum+=d[i];
		printf("%I64d\n",sum);
	}
	return 0;
}
/*
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50


46
210
*/