poj1860 Currency Exchange(bellman+spfa解法)_ 结构之美 算法之道

Bellman-Ford

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;

struct Node
{
    int s,e;
    double r,c;
    Node(int s_,int e_,double r_,double c_):s(s_),e(e_),r(r_),c(c_){}
};
double d[105];
int n,m,s;
double v;
vector<Node>G;

bool Bellman()
{
    memset(d,0,sizeof(d));
    d[s]=v;
    bool flag;
    for(int i=1;i<n;i++)
    {
        flag=false;
        for(int j=0;j<G.size();j++)
        {
            int s=G[j].s;
            int e=G[j].e;
            double r=G[j].r;
            double c=G[j].c;
            if(d[e]<(d[s]-c)*r)
            {
                d[e]=(d[s]-c)*r;
                flag=true;
            }
        }
        if(!flag) break;
    }
    for(int i=0;i<G.size();i++)
    {
        int s=G[i].s;
        int e=G[i].e;
        double r=G[i].r;
        double c=G[i].c;
        if(d[e]<(d[s]-c)*r)
            return true;
    }
    return false;
}

int main()
{
    int a,b;
    double rab,cab,rba,cba;
    //freopen("d:\test.txt","r",stdin);
    while(cin>>n>>m>>s>>v)
    {
        G.clear();
        for(int i=0;i<m;i++)
        {
            cin>>a>>b>>rab>>cab>>rba>>cba;
            G.push_back(Node(a,b,rab,cab));
            G.push_back(Node(b,a,rba,cba));
        }
        if(Bellman())
            cout<<"YES"<<endl;
        else
            cout<<"NO"<<endl;
    }
    return 0;
}
#include<iostream>
#inclu