题目链接：

题意是给你n种货币，下面m种交换的方式，拥有第s种货币V元。问你最后经过任意转换可不可能有升值。下面给你货币u和货币v，r1是u到v的汇率，c1是u到v的手续费，同理r2是v到u的汇率，c2是v到u的手续费。转换后的钱B = (转换之前的钱A - c) * r。

我用spfa做的，不断地松弛。要是存在正环，或者中间过程最初的钱升值了，就说明会升值。有负环的话，不满足松弛的条件，慢慢地就会弹出队列，也就不会升值。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 using namespace std; 6 const int MAXN = 1005; 7 struct data { 8     int next , to; 9     double r , c;10 }edge[MAXN * 3];11 int head[MAXN] , cont;12 double d[MAXN];13 14 void init(int n) {15     for(int i = 0 ; i <= n ; i++) {16         head[i] = -1;17         d[i] = 0;18     }19     cont = 0;20 }21 22 inline void add(int u , int v , double r , double c) {23     edge[cont].next = head[u];24     edge[cont].to = v;25     edge[cont].r = r;26     edge[cont].c = c;27     head[u] = cont++;28 }29 30 bool spfa(int s , double V) {31     queue 
         
           que;32     while(!que.empty()) {33         que.pop();34     }35     que.push(s);36     d[s] = V;37     while(!que.empty()) {38         int temp = que.front();39         que.pop();40         for(int i = head[temp] ; ~i ; i = edge[i].next) {41             double x = edge[i].r * (d[temp] - edge[i].c);42             if(x > d[edge[i].to]) {  //松弛43                 d[edge[i].to] = x;44                 que.push(edge[i].to);45                 if(d[s] > V) //增加则直接返回true46                     return true;47             }48         }49     }50     return false;51 }52 53 int main()54 {55     int n , m , s , u , v;56     double V , r , c;57     while(~scanf("%d %d %d %lf" , &n , &m , &s , &V)) {58         init(n);59         for(int i = 0 ; i < m ; i++) {60             scanf("%d %d %lf %lf" , &u , &v , &r , &c);61             add(u , v , r , c);62             scanf("%lf %lf" , &r , &c);63             add(v , u , r , c);64         }65         if(spfa(s , V))66             printf("YES\n");67         else68             printf("NO\n");69     }70 }