E

xuke123

题目大意：
汇率问题，有N个银行，他们之间有一些汇率，某个人手里面拿着其中一种钱，然后在这里面兑换钱币，当然兑换是有汇率和手续费的，然后经过一系列兑换后问手里面的钱是不是能增加？
integer A and B - numbers of currencies it exchanges, and real R AB, C AB, R BA and C BA - ？
这句话是每行有6个数，前面两个数是AB货币，依次往后是AB之间的汇率，AB之间的交易税，BA之间的汇率，BA之间的交易税

貌似这题就是专门为了spfa设计的啊。。。。。只要判断手持的这种货币是否增长了就行。


/////////////////////////////////////////////////////////////////////////

想法没错，不过无情的错了一次，而且还找了很长时间的BUG，最终发现原来是公式写错了....计算汇率的时候应该先减去佣金在乘上汇率....全是泪　　


#include<algorithm>
#include<queue>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
using namespace std;
const int maxn = 105;
const int oo = 0xfffffff;
struct node
{
    int B;
    double rate, commission;//汇率和佣金

    node(int B, double r, double c):B(B),rate(r),commission(c){}
};
vector<node> G[maxn];
double v[maxn];
int spfa(int k, double m)
{
    queue<int> Q;
    Q.push(k);
    while(Q.size())
    {
        int s = Q.front();
        Q.pop();
        int len = G.size();
        for(int i=0; i<len; i++)
        {
            node q = G;
            double p = (v-q.commission)*q.rate;
            if(p > v[q.B])
            {
                v[q.B] = p;
                Q.push(q.B);
            }
        }
        if(v[k] > m)
            return 1;
    }
    return 0;
}
int main()
{
    int N, M, s;
    double m;
    while(scanf("%d%d%d%lf", &N, &M, &s, &m) != EOF)
    {
        int i;
        for(i=1; i<=N; i++)
        {
            v = 0;
            G.clear();
        }
        v = m;
        int a, b;
        double rab, cab, rba, cba;
        for(i=0; i<M; i++)
        {
            scanf("%d%d%lf%lf%lf%lf", &a, &b, &rab, &cab, &rba, &cba);
            G[a].push_back(node(b, rab, cab));
            G.push_back(node(a, rba, cba));
        }
        int ans = spfa(s, m);
        //printf("%lf\n", v);

        if(ans == 1)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;　　}