版权声明：本文为博主原创文章，未经博主同意不得转载。 https://blog.csdn.net/u011775691/article/details/27612757

非常easy的bellmanford题目。这里比較具体：http://blog.csdn.net/lyy289065406/article/details/6645790

直接代码

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <cstring>

#include <cmath>

using namespace std;

const int SIZE=11111;

const int MAXLEN=1<<30;

struct sss

{

	int s,e,v;

}ed[SIZE];

int N,M,WH;

int dis[SIZE];

int ednum;

bool Bellman()

{

	for(int i=0;i<N-1;i++)

	{

		bool flag=false;

		for(int j=0;j<ednum;j++)

		{

			if(dis[ed[j].e]>dis[ed[j].s]+ed[j].v)

			{

				flag=true;

				dis[ed[j].e]=dis[ed[j].s]+ed[j].v;

			}

		}

		if(!flag)

			break;

	}

	for(int j=0;j<ednum;j++)

	{

		if(dis[ed[j].e]>dis[ed[j].s]+ed[j].v)

		{

			return true;

		}

	}

	return false;

}

int main()

{

	#ifndef ONLINE_JUDGE

		freopen("G:/1.txt","r",stdin);

		freopen("G:/2.txt","w",stdout);

	#endif

	int f,u,v,w;

	cin>>f;

	while(f--)

	{

		ednum=0;

		cin>>N>>M>>WH;

		for(int i=0;i<SIZE;i++)

		{

			dis[i]=MAXLEN;

		}

		for(int i=0;i<M;i++)

		{

			cin>>u>>v>>w;

			ed[ednum].s=u;

			ed[ednum].e=v;

			ed[ednum++].v=v;

			ed[ednum].e=u;

			ed[ednum].s=v;

			ed[ednum++].v=w;

		}

		for(int i=0;i<WH;i++)

		{

			cin>>u>>v>>w;

			ed[ednum].s=u;

			ed[ednum].e=v;

			ed[ednum++].v=-w;

		}

		if(Bellman())

			printf("YES\n");

		else

			printf("NO\n");

	}

    return 0;

}