最短路专题+spfa判断负环

题目链接：https://vjudge.net/problem/25713/origin
题目大意：有多种汇币，汇币之间可以交换，这需要手续费，当你用100A币交换B币时，A到B的汇率是29.75，手续费是0.39，那么你可以得到(100 - 0.39) * 29.75 = 2963.3975 B币。问s币的金额经过交换最终得到的s币金额数能否增加

货币的交换是可以重复多次的，如果有一个环使得某种货币一直增加，那么一定可以使得到的s币金额数增加，建图，一种货币就是一个点，货币交换作为有向边。spfa判断负环（一直可以松弛），松弛条件：(dis[d]-com[i])*rate[i]>dis[to[i]]

#include<cstdio>
#include<queue>
#include<vector>
#include<cstring>
#define MAXN 105
using namespace std;
int info[MAXN],cnt[MAXN];
double dis[MAXN];
bool flag[MAXN];
int src=0;
int n;
double v;
vector<int> to,next;
vector<double>com,rate;
queue<int> q;
void init()
{
	memset(info,-1,sizeof(info));
	memset(cnt,0,sizeof(cnt));
	memset(flag,false,sizeof(flag));
	memset(dis,0,sizeof(dis));
	next.clear();
	to.clear();
	com.clear();
	rate.clear();
}
void add(int i,int j,double r,double c)
{
	to.push_back(j);
	next.push_back(info[i]);
	info[i]=to.size()-1;
	com.push_back(c);
	rate.push_back(r);
}
bool spfa(int s,double v)
{
	int src=s-1;
	dis[src]=v;
	q.push(src);
	cnt[src]++;
	flag[src]=true;
	cnt[src]++;
	while(!q.empty())
	{
		int d=q.front();
		q.pop();
		flag[d]=false;
		for(int i=info[d];i!=-1;i=next[i])
		{
			if((dis[d]-com[i])*rate[i]>dis[to[i]])
			{
				dis[to[i]]=(dis[d]-com[i])*rate[i];
				if(!flag[to[i]])
				{
					q.push(to[i]);
					flag[to[i]]=true;
					cnt[to[i]]++;
					if(cnt[to[i]]>n)
					return true;
				}	
			}
		}
	}

	return false;
}
int main()
{
	int m,s;
	int a,b;
	double c,d,e,f;
	scanf("%d%d%d%lf",&n,&m,&s,&v);
	init();
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f);
		add(a-1,b-1,c,d);
		add(b-1,a-1,e,f);
	}
	if(spfa(s,v))
	printf("YES");
	else
	printf("NO");
	return 0;
	
}