#include<stdio.h>
struct Map
{
	double rate,c;
};
Map map[300][300];
double d[300];
int N,M,S;
double V;
int spfa(int s)
{
	int q[300];
	int v[300],i,x=0,j,h=0,t=1;
	for(i=0;i<300;i++)
	{
		q[i]=v[i]=0;
		d[i]=0;
	}
	d[s]=V;v[S]=1;
	q[t]=s;
	
	count++;
	while(h!=t)
	{
		h=(h+1)%(N+1);
		x=q[h];
		v[x]=0;
		for(i=1;i<=N;i++)
		{
			if(d[i]<(d[x]-map[x][i].c)*map[x][i].rate)
			{
				d[i]=(d[x]-map[x][i].c)*map[x][i].rate;
				if(v[i]==0)
				{
					t=(t+1)%(N+1);
					q[t]=i;
					v[i]=1;
				}
			}
		}		
	}
	if(d[s]>V)
		return 1;
	else return 0;
}
int main()
{
	int i,j,a,b;
	double rab,rba,cab,cba;
	scanf("%d%d%d%lf",&N,&M,&S,&V);
		for(i=0;i<M;i++)
		{
			scanf("%d%d%lf%lf%lf%lf",&a,&b,&rab,&cab,&rba,&cba);
			map[a][b].rate=rab;
			map[a][b].c=cab;
			map[b][a].rate=rba;
			map[b][a].c=cba;
		}
		if(spfa(S)==1)
			printf("YES\n");
		else
			printf("NO\n");
	return 0;
}

• Re:用spfa过的 (14) lin5547 2012-04-19 23:27:04
  • Re:用spfa过的 (83) 1120102012 2012-05-29 21:50:29
    • 这是碰巧过的吧 (61) Mikucon 2012-07-09 11:19:56