2009-2-18-pku2983.txt

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

#include<stdio.h>
const int MAXV=1005;
const int MAXE=300005;
const int INF=100000000;
typedef struct Edge
{
	int st;
	int ed;
	int distance;
}Edge;
Edge edge[MAXE];
int d[MAXV];
//初始化d[u]：用来描述从源点S到u的最短路径上权值的三界！
void Init(int V,int S)
{
	int i;
	for(i=1;i<=V;i++)
		d[i]=INF;//开始的时候设置为无穷大!
	d[S]=0;//源点设置为0
}
//Bellman_Ford算法的实现!
bool Bellman_Ford(int V,int E,int S)
{
	int i,j;
	bool relaxed;//优化
	Init(V,S);
	for(i=1;i<=V-1;i++)
	{
		relaxed=true;
		for(j=1;j<=E;j++)
			if(d[edge[j].ed]>d[edge[j].st]+edge[j].distance)
				d[edge[j].ed]=d[edge[j].st]+edge[j].distance,relaxed=false;
		if(relaxed)//说明当前这一轮没有进行松弛，那么以后将也不会进行松弛，那么就提前结束！
			break;
	}
	return relaxed;
}
int main()
{
	int V,E,i,n;
	int st,ed,distance;
	char ch;
	while(scanf("%d%d",&V,&n)!=EOF)
	{
		getchar();
		E=0;
		for(i=1;i<=n;i++)
		{
		   scanf("%c",&ch);
	 	   if(ch=='P')
		   {
			 scanf("%d%d%d",&st,&ed,&distance);
			 getchar();
			 edge[++E].st=st;
			 edge[E].ed=ed;
			 edge[E].distance=-distance;

			 edge[++E].st=ed;
			 edge[E].ed=st;
			 edge[E].distance=distance;
		   }
		  else
		  {
			scanf("%d%d",&st,&ed);
			edge[++E].st=st;
			edge[E].ed=ed;
			edge[E].distance=-1;
			getchar();
		  }
		}
		if(Bellman_Ford(V,E,1))
			printf("Reliable\n");
		else
			printf("Unreliable\n");
	}
	return 0;
}
/*
3 4
P 1 2 1
P 2 3 1
V 1 3
P 1 3 1
5 5
V 1 2
V 2 3
V 3 4
V 4 5
V 3 5

Unreliable
Reliable
*/