poj1860Currency Exchange

 1 #include <iostream>
 2 #include <cstring>
 3 #include <stdio.h>
 4 
 5 using namespace std;
 6 
 7 int n,m,s,all;
 8 double v;
 9 double dis[110];
10 class exchange_point
11 {
12 public:
13     int a,b;
14     double r,c;
15 }point[210];
16 bool BF()
17 {
18     memset(dis,0,sizeof(dis));
19     dis[s]=v;
20     bool flag;
21     for(int i=1;i<=n-1;i++)
22     {
23         flag=false;
24         for(int j=0;j<all;j++)
25         {
26             if(dis[point[j].b]<(dis[point[j].a]-point[j].c)*point[j].r)
27             {
28                 dis[point[j].b]=(dis[point[j].a]-point[j].c)*point[j].r;
29                 flag=true;
30             }
31         }
32         if(flag==false)
33             break;
34     }
35         for(int k=0;k<all;k++)
36         {
37             if(dis[point[k].b]<(dis[point[k].a]-point[k].c)*point[k].r)
38             {
39                 return true;
40             }
41         }
42         return false;
43 }
44 int main()
45 {
46     double rab,cab,rba,cba;
47     int a,b;
48     while(~scanf("%d%d%d%lf",&n,&m,&s,&v))
49     {
50         all=0;
51         for(int i=0;i<m;i++)
52         {
53             cin>>a>>b>>rab>>cab>>rba>>cba;
54             point[all].a=a;
55             point[all].b=b;
56             point[all].r=rab;
57             point[all++].c=cab;
58             point[all].a=b;
59             point[all].b=a;
60             point[all].r=rba;
61             point[all++].c=cba;
62         }
63         if(BF())
64             printf("YES
");
65         else
66             printf("NO
");
67     }
68     return 0;
69 }