2009-2-19-pku1860.txt

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

#include<stdio.h>
const int MAXV=105;
const int MAXE=1005;
const double EPS=1e-8;
const double INF=1e100;
typedef struct Edge
{
	int st;

	int ed;
	double r;//汇率
	double c;//佣金
}Edge;
Edge edge[MAXE];
double d[MAXV];
void Init(int V,int S)
{
	int i;
	for(i=1;i<=V;i++)
		d[i]=0;
	//d[S]=0;
}
bool Bellman_Ford(int V,int E,int S,double val)
{
	int i,j;
	bool relaxed;
	Init(V,S);
	d[S]=val;
	while(d[S]<=val+EPS)
	{
		relaxed=false;
		for(j=1;j<=E;j++)
			if(d[edge[j].ed]+EPS<(d[edge[j].st]-edge[j].c)*edge[j].r)
				d[edge[j].ed]=(d[edge[j].st]-edge[j].c)*edge[j].r,relaxed=true;
		if(!relaxed)
			return d[S]>val;
	}
	return true;
}
int main()
{
	int V,E,S,i,n;
	int st,ed;
	double r1,r2,c1,c2;
	double val;
	while(scanf("%d%d%d%lf",&V,&n,&S,&val)!=EOF)
	{
		E=0;
		for(i=1;i<=n;i++)
		{
			scanf("%d%d%lf%lf%lf%lf",&st,&ed,&r1,&c1,&r2,&c2);
			edge[++E].st=st;
			edge[E].ed=ed;
			edge[E].r=r1;
			edge[E].c=c1;

			edge[++E].st=ed;
			edge[E].ed=st;
			edge[E].r=r2;
			edge[E].c=c2;
		}
		if(Bellman_Ford(V,E,S,val))
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}		
/*
3 2 1 20.0
1 2 1.00 1.00 1.00 1.00
2 3 1.10 1.00 1.10 1.00


YES
*/