刚上来一堆英文着实有点蒙逼，仔细分析是一个Bellman的变形，只要能找出一个无限增大的环这个题就好解决了，我这里用的SPFA，用邻接链表进行储存，直接套用的模板，部分变量名字没有改的很好
#include <iostream>
#include<string.h>
#include <queue>
#include <vector>
using namespace std;
#define MAX 99999999;
double dis[1000+6];
double vis[1000+6];
int n;
double fir;
typedef struct
{
int x;
double rate;
double cost;
}point;
vector<point> p[1010];
int Spfa(int start)
{
queue<int> Q;
memset(vis, 0, sizeof(vis));
memset(dis, 0, sizeof(dis));
dis[start] = fir;
vis[start] = true;
Q.push(start);
while (!Q.empty()){
int temp = Q.front();
Q.pop();
vis[temp] = false;
for(int i=0; i<p[temp].size(); i++)
{
int v=p[temp][i].x;
double w=p[temp][i].rate;
double z=p[temp][i].cost;
if ((dis[temp]-z)*w > dis[v])
{
dis[v] = (dis[temp]-z)*w;
if(dis[start]>fir)
return true;
if (!vis[v])
{
Q.push(v);
vis[v] = true;
}
}
}
}
return false;
}
int main()
{
int m,s;
while(cin>>n>>m>>s>>fir)
{
point node;
int from,to;
double rab,rba,cab,cba;
for(int i=0;i<m;i++)
{
cin>>from>>to>>rab>>cab>>rba>>cba;
node.x=to;
node.rate=rab;
node.cost=cab;
p[from].push_back(node);
node.x=from;
node.rate=rba;
node.cost=cba;
p[to].push_back(node);
}
int flag=0;
flag=Spfa(s);
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO
";
for(int i=1;i<n;i++)
p[i].clear();
}
return 0;
}