poj-1860 Currency Exchange **

小雪崩

/*
* 汇率问题： Bellman_Ford算法 ， 判断正环
*
* 有个奇怪的问题： 如果把 d初始化为 -inf 则 WA， 初始化为 0 或 -100 之类的值则AC~  奇怪
*/
#include <iostream>
#include <cstring>
using namespace std;
const int maxN = 100 + 5;
int n, m, s;
double v, r[maxN][maxN], c[maxN][maxN], d[maxN];
void ini(){
    for(int i=1; i<=n; i++)
        d = 0;
    d = v;
}
/*
bool relax(int lhs, int rhs){
    double tmp = (d[lhs] - c[lhs][rhs]) * r[lhs][rhs];
    if(tmp >= eps && d[rhs] < tmp + eps){
        d[rhs] = tmp;
        return 1;
    }
    return 0;
}
*/
bool Bellman_Ford(){
    ini();
    bool flag;
    for(int i=1; i<=n; i++){
        flag = 0;
        for(int j=1; j<=n; j++){
            for(int k=1; k<=n; k++){
                if(r[j][k] >= 0)
                    if(d[k] < (d[j] - c[j][k]) * r[j][k]){
                        d[k] = (d[j] - c[j][k]) * r[j][k];
                        flag = 1;
                    }
            }
        }
        if(!flag) break;        //没有边能继续松弛
    }
    //判断正环
    for(int j=1; j<=n; j++){
        for(int k=1; k<=n; k++){
            if(r[j][k] >= 0 && d[k] < (d[j] - c[j][k]) * r[j][k]){
                return 1;
            }
        }
    }
    return 0;
}

int main(){
    while(cin >> n >> m >> s >> v){
    for(int i=0; i<=n; i++)
        for(int j=0; j<=n; j++)
            r[j] = -1;

    int a, b;
    for(int i=1; i<=m; i++){
        cin >> a >>b;
        cin >> r[a] >> c[a] >> r[a] >> c[a];
    }
    if(Bellman_Ford())
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
    }
    return 0;
}