//这是一道判断有无负环的题目，主要是为了熟悉bellman-Ford算法，写法也是采用模板题的写法

#include <iostream>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

int f,n,m,w,all_e;

int dis[];

struct node{

    int s;

    int e;

    int t;

} edge[];

bool bellman_ford()

{

    bool flag;

    for(int i=; i<n-; i++)

    {

        flag=false;

        for(int j=; j<all_e; j++)

            if(dis[edge[j].e] > dis[edge[j].s] + edge[j].t)

            {

                dis[edge[j].e] = dis[edge[j].s] + edge[j].t ;

                flag=true;

            }

        if(!flag)

            break;

    }

    for(int j=; j<all_e; j++)

            if(dis[edge[j].e] > dis[edge[j].s] + edge[j].t)

                return true;        

    return false;

}

int main ()

{

    cin>>f;

    while(f--)

    {

        memset(dis, 0x3f, sizeof(dis));

        cin>>n>>m>>w;

        all_e=;

        int u,v,c;

        for(int i=; i<m; i++)

        {

            cin>>u>>v>>c;

            edge[all_e].s=edge[all_e+].e=u;

            edge[all_e].e=edge[all_e+].s=v;

            edge[all_e].t=edge[all_e+].t=c;

            all_e=all_e+;

        }

        for(int i=; i<w; i++)

        {

            cin>>u>>v>>c;

            edge[all_e].s=u;

            edge[all_e].e=v;

            edge[all_e].t=-c;

            all_e++;

        }

        if(bellman_ford())

            cout<<"YES"<<endl;

        else

            cout<<"NO"<<endl;

    }

    return ;

}

我们城市有几个货币兑换点在运作。假设每个点专门处理两种特定的货币，并且只对这些货币执行兑换操作。可以有几个点专门针对同一种货币。每个点都有自己的汇率，A到B的汇率是1A的B的数量。另外，每个兑换点都有一定的佣金，你必须为你的兑换业务支付的金额。佣金总是以货币量收取。
例如，如果你想在兑换点将100美元兑换成俄罗斯卢布，汇率为29.75，佣金为0.39，你将得到(100-0.39)*29.75=2963.3975RUR。
你当然知道，在我们的城市里，你可以对付N种不同的货币。让我们为每种货币分配从1到N的唯一整数。然后，每个交换点可以用6个数字来描述：整数A和B-它交换的货币数和实R。_AB型、C_AB型，R_巴和C_巴-交换A至B和B至A时的汇率和佣金。
尼克有一些货币S，他想知道他是否可以某种方式，在一些外汇操作后，增加他的资本。当然，他最终想把钱换成S货币。帮助他回答这个难题。尼克在做手术的时候总要有一笔非负的钱。

输入的第一行包含四个数字：n-货币数量，M-外汇点数，S-货币尼克的数量，V-他拥有的货币单位的数量。以下M行按上述顺序分别包含6个数字-对应的交换点的描述。数字由一个或多个空格分隔。1<=S<=N<=100，1<=M<=100，V为实数，0<=V<=10³. 
每一点的汇率和佣金是真实的，小数点之后最多有两位数，即10。^-2<=rate<=10²，0<=佣金<=10². 
如果在这个序列中没有不止一次使用交换点，那么让我们简单地调用交换操作的某些序列。您可以假设，在任何简单的交换操作序列的末尾和开始处的数字值的比率将小于10。⁴. 

如果尼克能增加他的财富，产出是肯定的，在其他情况下输出不输出文件。

3 2 1 20.0

1 2 1.00 1.00 1.00 1.00

2 3 1.10 1.00 1.10 1.00

YES

//该题刚刚写的时候，不知道怎么处理这些数据，把这些数据看成图，其实本质都是一样的，只不给边赋予了性质，处理好这些数据又是一道模板题

#include <iostream>

#include <cstring>

using namespace std;

int g1[][]={},g2[][]={};

double dis[]={};

int n,m,s;

double v;

struct node{

    int a,b;

    double ha,hb;

    double ya,yb;

}edge[];

bool bellman_ford()

{

    bool flag=false;

    for(int i=; i<n-; i++)

    {

        flag=false;

        for(int j=; j<*m; j++)

        {

            if((dis[edge[j].a]-edge[j].ya)*edge[j].ha>dis[edge[j].b])

            {

                dis[edge[j].b]=(dis[edge[j].a]-edge[j].ya)*edge[j].ha;

                flag=true;

            }

        }

        if(!flag)

            break;

    }

    for(int j=; j<*m; j++)

    {

        if((dis[edge[j].a]-edge[j].ya)*edge[j].ha>dis[edge[j].b])

        {

            dis[edge[j].b]=(dis[edge[j].a]-edge[j].ya)*edge[j].ha;

            return true;

        }

    }

    return false;

}

int main()

{

    cin>>n>>m>>s>>v;

    dis[s]=v;

    for(int i=; i<*m; i=i+)

    {

       cin>>edge[i].a>>edge[i].b>>edge[i].ha>>edge[i].ya>>edge[i].hb>>edge[i].yb;

       edge[i+].b=edge[i].a, edge[i+].a=edge[i].b;

       edge[i+].ha=edge[i].hb, edge[i+].hb=edge[i].ha;

       edge[i+].ya=edge[i].yb, edge[i+].yb=edge[i].ya;

    }

    if(bellman_ford())

        cout<<"YES"<<endl;

    else

        cout<<"NO"<<endl;

    return ;

}