【最短路】 ZOJ 1544 Currency Exchange 推断负圈

给出 N 种货币 M 条兑换关系 開始时全部的货币S 和有X 块钱

接下来M条关系

A B W1 W2 W3 W4

表示

A->B 所需的手续费为W2块钱  汇率为W1

B->A 所需的手续费为W4块钱  汇率为W3

所以对于输入的一行建两条边

要求到最后能够赚到钱

所以当出现了负圈就可以赚到无限多的钱

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <climits>

#include <cctype>

#include <cmath>

#include <string>

#include <sstream>

#include <iostream>

#include <algorithm>

#include <iomanip>

using namespace std;

#include <queue>

#include <stack>

#include <vector>

#include <deque>

#include <set>

#include <map>

typedef long long LL;

#pragma comment(linker, "/STACK:1024000000,1024000000")

#define pi acos(-1.0)

#define lson l, m, rt<<1

#define rson m+1, r, rt<<1|1

typedef pair<int, int> PI;

typedef pair<int, PI> PP;

#ifdef _WIN32

#define LLD "%I64d"

#else

#define LLD "%lld"

#endif

//LL quick(LL a, LL b){LL ans=1;while(b){if(b & 1)ans*=a;a=a*a;b>>=1;}return ans;}

//inline int read(){char ch=' ';int ans=0;while(ch<'0' || ch>'9')ch=getchar();while(ch<='9' && ch>='0'){ans=ans*10+ch-'0';ch=getchar();}return ans;}

//inline void print(LL x){printf(LLD, x);puts("");}

//inline void read(int &x){char c = getchar();while(c < '0') c = getchar();x = c - '0'; c = getchar();while(c >= '0'){x = x * 10 + (c - '0'); c = getchar();}}

const int INF=0x3f3f3f3f;

const int MAXN=550;

double dist[MAXN];

struct Edge

{

    int u,v;

    double a,b;

    Edge(int _u=0,int _v=0,double _a=0,double _b=0):u(_u),v(_v),a(_a),b(_b) {}

};

vector<Edge>E;

bool bellman_ford(int start,int n,double x)

{

    for(int i=1; i<=n; i++)

        dist[i]=0;

    dist[start]=x;

    for(int i=1; i<n; i++)

    {

        bool flag=false;

        for(int j=0; j<E.size(); j++)

        {

            int u=E[j].u;

            int v=E[j].v;

            double a=E[j].a;

            double b=E[j].b;

            if(dist[v]<(dist[u]-b)*a)

            {

                dist[v]=(dist[u]-b)*a;

                flag=true;

            }

        }

        if(!flag)

            return true;//没有负环回路

    }

    for(int j=0; j<E.size(); j++)

        if(dist[E[j].v]<(dist[E[j].u]-E[j].b)*E[j].a)

            return false;//有负环回路

    return true;//没有负环回路

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("in.txt", "r", stdin);

    freopen("out.txt", "w", stdout);

#endif

    int n,m,s;

    double x;

    while(scanf("%d%d%d%lf",&n,&m,&s,&x)!=EOF)

    {

        int a,b;

        double w1,w2,w3,w4;

        E.clear();

        for(int i=0; i<m; i++)

        {

            scanf("%d%d%lf%lf%lf%lf",&a,&b,&w1,&w2,&w3,&w4);

            E.push_back(Edge(a,b,w1,w2));

            E.push_back(Edge(b,a,w3,w4));

        }

        if(bellman_ford(s,n,x))

            printf("NO\n");

        else puts("YES");

     }

    return 0;

}