View Code of Problem 128

//Bellman-Ford算法 
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 1000000000
using namespace std;
int m,n;
typedef struct Node{
	int v,dis;
	Node(int _v,int _dis):v(_v),dis(_dis){}
}Node;
bool Bellman(int s,vector<Node> adj[]){
	int d[n];
	fill(d,d+n,INF);
	d[s]=0;
	for(int i=0;i<n-1;i++){
		for(int u=1;u<=n;u++){
			for(int j=0;j<adj[u].size();j++){
				int v=adj[u][j].v;
				int dis=adj[u][j].dis;
				if(d[u]+dis<d[v]){
					d[v]=d[u]+dis;
				}
			}
		}
	}
	for(int u=1;u<=n;u++){
		for(int j=0;j<adj[u].size();j++){
			int v=adj[u][j].v;
			int dis=adj[u][j].dis;
			if(d[u]+dis<d[v]){
				return true;
			}
		}
	}
	if(d[n]<0)	return true;
	else return false;
} 
int main(){
	while(cin>>n>>m){
		vector<Node> adj[n+1];
		for(int i=0;i<m;i++){
			int a,b,c;
			cin>>a>>b>>c;
			adj[a].push_back(Node(b,c));
		}
		bool flag=Bellman(1,adj);
		if(flag)	cout<<"YES"<<endl;
		else 		cout<<"NO"<<endl;	
	}
}