学步园

判断最长路径是否有正环即可

#include<iostream>
#include<cstring>
#include<cstdlib>
using namespace std;
struct node
{
	int a,b;
	double rab,cab,rba,cba;
};
node ex[101];
bool bellmanford(int s,double sw,int v,int e)
{
	double dis[101];
	int i;
	bool flag;
	memset(dis,0,sizeof(dis));
	dis[s]=sw;
	while(v--)
	{
		flag=1;
		for(i=1;i<=e;i++)
		{
			if((dis[ex[i].b]-ex[i].cba)*ex[i].rba>dis[ex[i].a])
			{
				dis[ex[i].a]=(dis[ex[i].b]-ex[i].cba)*ex[i].rba;
				flag=0;
			}
			if((dis[ex[i].a]-ex[i].cab)*ex[i].rab>dis[ex[i].b])
			{
				dis[ex[i].b]=(dis[ex[i].a]-ex[i].cab)*ex[i].rab;
				flag=0;
			}
		}
		if(flag)
		{
			return 0;
		}
	}
	return 1;
}
int main()
{
	int i,n,m,s;
	double v;
	scanf("%d%d%d%lf",&n,&m,&s,&v);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%lf%lf%lf%lf",&ex[i].a,&ex[i].b,&ex[i].rab,&ex[i].cab,&ex[i].rba,&ex[i].cba);
	}
	if(bellmanford(s,v,n,m))
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	//system("Pause");
}