spfa（判负环变形）

题目链接
题意：n种货币，m种交换、s、v 。边：u、v、r1、c1、r2、c2表示u货币换成v货币需要c1手续费和交换率r1,v换u为c2,r2.(转换公式：val[v] = (val[u]-c1)r1)
初始有s货币v枚。问能否通过一系列的交换，可以获得比初始更多的钱？
解法：最短路径的变形。dis初始化为0，如果通过转换可以获得比以前更多的钱，则更新。
spfa判负环：更新超过n-1次则有负环（入队超过n次）。

//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#include <stdlib.h>
using namespace std;
typedef long long ll ;
#define int ll
#define mod 100
#define gcd(m,n) __gcd(m, n)
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j)  for(int i = n ; i >= j ; i--)
#define ME(x , y) memset(x , y , sizeof(x))
//int lcm(int a , int b){return a*b/gcd(a,b);}
//ll quickpow(ll a , ll b){ll ans=1;while(b){if(b&1)ans=ans*a%mod;b>>=1,a=a*a%mod;}return ans;}
//int euler1(int x){int ans=x;for(int i=2;i*i<=x;i++)if(x%i==0){ans-=ans/i;while(x%i==0)x/=i;}if(x>1)ans-=ans/x;return ans;}
//const int N = 1e7+9; int vis[n],prime[n],phi[N];int euler2(int n){ME(vis,true);int len=1;rep(i,2,n){if(vis[i]){prime[len++]=i,phi[i]=i-1;}for(int j=1;j<len&&prime[j]*i<=n;j++){vis[i*prime[j]]=0;if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}else{phi[i*prime[j]]=phi[i]*phi[prime[j]];}}}return len}
#define INF  0x3f3f3f3f
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
#define lson l,mid,root<<1
#define rson mid+1,r,root<<1|1
#define pb push_back
#define mp make_pair
#define all(v) v.begin(),v.end()
#define size(v) (int)(v.size())
#define cin(x) scanf("%lld" , &x);
const int N = 1e4+9;
const int maxn = 1e3+9;
const double esp = 1e-6;
int head[maxn] , tol ;
int n , m , s ;
double v;
int vis[maxn] , ans[maxn];
double dis[maxn];
struct node{
    int to;
    double w , p;
    int next;
}g[maxn<<1];
void add(int u , int v , double w , double p){
    g[++tol] = {v , w , p , head[u]};
    head[u] = tol;
}

bool spfa(int u){
    ME(vis , 0);
    fill(dis , dis+maxn , 0);
    dis[u] = v; vis[u] = 1 ;
    ans[u]++;
    queue<int>q;
    q.push(u);
    while(!q.empty()){
        int a = q.front();q.pop();
        vis[a] = 0 ;
        for(int i = head[a] ; i ; i = g[i].next){
            int to = g[i].to ;
            double w = g[i].w ;
            double p = g[i].p ;
            if((dis[a]-p)*w > dis[to]){
                dis[to] = (dis[a]-p)*w;
                if(!vis[to]){
                    vis[to] = 1;
                    q.push(to);
                    ans[to]++;
                    if(ans[to] > n){
                        return false;
                    }
                }
            }
        }
    }
    return true;
}

void init(){
    tol = 0 ;
    ME(head, 0);
    ME(ans , 0);
}
void solve(){
    init();
    scanf("%lld%lld%lld%lf" , &n , &m , &s , &v);
    rep(i , 1 , m){
        int u , v ;
        double w , p ;
        scanf("%lld%lld%lf%lf" , &u , &v , &w , &p);
        add(u , v , w , p);
        scanf("%lf%lf" , &w , &p);
        add(v , u , w , p);
    }
    if(spfa(s)){
        cout << "NO" << endl;
    }else{
        cout << "YES" << endl;
    }
}

signed main()
{
    //ios::sync_with_stdio(false);

    solve();

}