[POJ] 1860 Currency Exchange.cpp

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
int main()
{
    int N, M, S;
    double V;
    double R[101][101] = {0};
    double C[101][101];
    vector<int> toNxt[101];

    // Input
    scanf("%d %d %d %lf", &N, &M, &S, &V);

    int a, b; double Rab, Rba, Cab, Cba;
    for (int i = 0; i < M; ++i) {
        scanf("%d %d %lf %lf %lf %lf", &a, &b, &Rab, &Cab, &Rba, &Cba);
        R[a][b] = Rab; R[b][a] = Rba;
        C[a][b] = Cab; C[b][a] = Cba;
        toNxt[a].push_back(b);
        toNxt[b].push_back(a);
    }

    // SPFA
    double Dis[101] = {0};
    queue<int> Q;
    bool inQueue[101] = {0};

    Dis[S] = V;
    Q.push(S);
    inQueue[S] = true;

    while (!Q.empty()) {
        int now = Q.front();
        inQueue[now] = false;
        Q.pop();

        for (int i = 0; i < toNxt[now].size(); ++i) {
            int nxt = toNxt[now][i];
            if (Dis[nxt] < (Dis[now]-C[now][nxt])*R[now][nxt]) {
                Dis[nxt] = (Dis[now]-C[now][nxt])*R[now][nxt];
                if (!inQueue[nxt]) {
                    Q.push(nxt);
                    inQueue[nxt] = true;
                }
            }
        }
    }

    // Analysis & Output
    if (Dis[S] > V) puts("YES");
    else puts("NO");
}