pku 1860 Currency Exchange

dong5300

　　题意：
　　第一行：货币的总的种类，货币中心的数量，所持有的货币种类，持有该种类货币的数量
　　后M行：货币a，货币b，汇率Rab， 手续费Cab， 汇率Rba， 手续费Cba
　　思路：用spfa找到，看是否有负权回路（用count[]计数，记录每个结点进队次数，超过|n|次表示有负权），如果有，则表示可以一直增加自己的钱，用bellman也可以实现
　　虽然是A了，感觉数据挺弱……
　　比较郁闷的是小号交47ms，大号交79ms   - -|||
　　调了很久，最后很没脾气的加了eps，然后没有编译直接小号交了，居然A了……
　　code：



#include <iostream>
#include <cstdio>
#include <climits>
#include <queue>
#include <cstring>
#define eps 1e-6
using namespace std;
const int MAXN=105;
int m, n, type;
double money;
struct Node
{
    double r, c;
}map[MAXN][MAXN];
int count[MAXN];
bool spfa(int s, int e)
{
    queue<int> q;
    double dist[MAXN];
    bool vis[MAXN];
    memset(vis, 0, sizeof(vis));
    memset(count, 0, sizeof(count));
    for(int i=1; i<=n; i++)
        dist=0;
    dist=money;
    vis=1;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        if(count[x]>n) return 0;
        vis[x]=0;
        for(int i=1; i<=n; i++)
            if((dist[x]-map[x].c)*map[x].r>dist+eps)
            {
                dist=(dist[x]-map[x].c)*map[x].r;
                if(!vis)
                {
                    vis=1;
                    q.push(i);
                    count++;
                }
            }
    }
    return 1;
}
int main()
{
    while(scanf("%d%d%d%lf", &n, &m, &type, &money)!=EOF)
    {
        for(int i=0; i<m; i++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            scanf("%lf%lf%lf%lf", &map[x][y].r, &map[x][y].c, &map[y][x].r, &map[y][x].c);
        }
        int flag;
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                flag=spfa(j, i);
                if(!flag) break;
            }
        }
        if(!flag) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}