主要找正环:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#define MAXN 52000
using namespace std;
const int INF=-<<;
bool vis[MAXN];
int head[MAXN];
int next[MAXN];
int s;
double dis[MAXN];
struct node
{
int u,v;
double r,c;
}p[MAXN];
int e,n,m;
int cnt[MAXN];
double v;
void addnode(int u,int v,double r,double c)
{
p[e].u=u;
p[e].v=v;
p[e].r=r;
p[e].c=c;
next[e]=head[u];
head[u]=e++;
}
bool relax(int u,int v,double r,double c)
{
if(dis[v]<(dis[u]-c)*r)
{
dis[v]=(dis[u]-c)*r;
return true;
}
return false;
}
bool spfa(int rc)
{
memset(vis,false,sizeof(vis));
memset(cnt,,sizeof(cnt));
for(int i=;i<=n;i++)
dis[i]=;
dis[rc]=v;
vis[rc]=true;
queue<int>q;
q.push(rc);
++cnt[rc];
while(!q.empty()){
int pre=q.front();
q.pop();
vis[pre]=false;
for(int i=head[pre];i+;i=next[i])
{
if(relax(pre,p[i].v,p[i].r,p[i].c)&&!vis[p[i].v]){
if((++cnt[p[i].v])>n) return false;
q.push(p[i].v);
vis[p[i].v]=true;
}
}
}
return true;
}
int main()
{
memset(head, -, sizeof(head));
memset(next, -, sizeof(next));
e=;
int a,b;
double r1,c1,r2,c2;
scanf("%d%d%d%lf",&n,&m,&s,&v);
for(int i=;i<m;i++){
scanf("%d%d%lf%lf%lf%lf",&a,&b,&r1,&c1,&r2,&c2);
addnode(a,b,r1,c1);
addnode(b,a,r2,c2);
}
if(!spfa(s)) printf("YES\n");
else printf("NO\n");
return ;
}