题意：

现在有n种类型（1-n）的货币， m个城市，每个城市你可以 将a货币换成b货币, 汇率为r， 每换一次要先收取佣金c

现在先输入n， m,    s(代表你一开始拥有的货币类型)， v（你所拥有的货币量）

输入m行

aa, bb, r1, c1, r2, c2  货币aa换成货币bb的汇率为 r1, 佣金为c1， 货币bb换成货币aa的汇率为 r2, 佣金为c2

请问存不存在兑换若干次后， 存在钱的价值增加（即正权回路）

题解：

一般负权回路，我们用bellman-ford算法，判断正权回路也可，只要把松弛操作和初始化改一下即可

求最小路径 变为 求最大路径

AC_code:

/*
Algorithm:bellman-ford
Author: anthony1314
Creat Time:
Time Complexity:
*/

#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<cstdio>
//#include<bits/stdc++.h>
#define ll long long
#define maxn 1005
#define mod 1e9 + 7
#define line printf("--------------");
using namespace std;
int n, m, s;
int tot;
double v, dis[105];
struct node {
	int a, b;
	double r, c;
} edge[205];//边的结构体
bool bellmanford() {
	memset(dis, 0, sizeof(dis));//先初始化为最小
	dis[s] = v;
	bool flag;
	for(int i = 1; i < n; i++) {
		flag = false;
		for(int j = 0; j < tot; j++) {
			if(dis[edge[j].b] < (dis[edge[j].a] - edge[j].c) * edge[j].r) { //松弛操作
				flag = true;
				dis[edge[j].b] = (dis[edge[j].a] - edge[j].c) * edge[j].r;
			}
		}
		if(!flag) {
			return false;
		}
	}
	for(int i = 0; i < tot; i++) {
		if(dis[edge[i].b] < (dis[edge[i].a] - edge[i].c) * edge[i].r) {
			return true;
		}
	}
	return false;
}
int main() {
	while(cin>>n>>m>>s>>v) {
		tot = 0;
		int aa, bb;
		double r1, c1, r2, c2;
		for(int i = 0; i < m; i++) {
			scanf("%d %d %lf %lf %lf %lf", &aa, &bb, &r1, &c1, &r2, &c2);
			edge[tot].a = aa;
			edge[tot].b = bb;
			edge[tot].r = r1;
			edge[tot++].c = c1;
			edge[tot].a = bb;
			edge[tot].b = aa;
			edge[tot].r = r2;
			edge[tot++].c = c2;
		}
		if(bellmanford()) {
			cout<<"YES"<<endl;
		} else {
			cout<<"NO"<<endl;
		}
	}
	return 0;
}