【最短路】 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, &quot;/STACK:1024000000,1024000000&quot;)
#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 &quot;%I64d&quot;
#else
#define LLD &quot;%lld&quot;
#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(&quot;&quot;);}
//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=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-b)*a)
{
dist[v]=(dist-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(&quot;in.txt&quot;, &quot;r&quot;, stdin);
freopen(&quot;out.txt&quot;, &quot;w&quot;, stdout);
#endif
int n,m,s;
double x;
while(scanf(&quot;%d%d%d%lf&quot;,&n,&m,&s,&x)!=EOF)
{
int a,b;
double w1,w2,w3,w4;
E.clear();
for(int i=0; i<m; i++)
{
scanf(&quot;%d%d%lf%lf%lf%lf&quot;,&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(&quot;NO\n&quot;);
else puts(&quot;YES&quot;);
}
return 0;
}