#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define eps 1e-10
struct Node
{
double rate, com;
int link;
Node(){}
Node( double a, double b, int c ): rate(a), com(b), link(c){}
};
Node map[110][110];
double v, result[110];
int m, n, s;
bool bellman()
{
memset( result, 0, sizeof(result) );
result[s]= v;
while( result[s]<= v+ eps )
{
bool ok= false;
for( int i= 1; i<= n; ++i )
for( int j= 1; j<= n; j++ )
if( map[i][j].link> 0 && result[j]+ eps< ( result[i]- map[i][j].com ) * map[i][j].rate )
{
result[j]= ( result[i]- map[i][j].com ) * map[i][j].rate;
ok= true;
}
if( !ok ) break;
}
if( result[s]> v+ eps ) return true;
else return false;
}
int main()
{
while( scanf("%d%d%d%lf", &n, &m, &s, &v)!= EOF )
{
for( int i= 0; i<= n; ++i )
for( int j= 0; j<= n; ++j ) map[i][j].link= 0;
for( int i= 0; i< m; ++i )
{
int a, b;
double r1,c1,r2,c2;
scanf("%d%d%lf%lf%lf%lf", &a, &b, &r1, &c1, &r2, &c2 );
map[a][b]= Node( r1, c1, 1 );
map[b][a]= Node( r2, c2, 1 );
}
if( bellman() ) printf("YES\n");
else printf("NO\n");
}
return 0;
}
posted on 2008-11-06 20:26
Darren 閱讀(414)
評(píng)論(0) 編輯 收藏 引用