#include <cstdlib> #include <cctype> #include <cstring> #include <cstdio> #include <cmath> #include <algorithm> #include <vector> #include <string> #include <iostream> #include <sstream> #include <map> #include <set> #include <queue> #include <stack> #include <fstream> #include <numeric> #include <iomanip> #include <bitset> #include <list> #include <stdexcept> #include <functional> #include <utility> #include <ctime> #define PB push_back #define MP make_pair #define FOR1(n) for(int i=0;i<(n);++i) #define FOR2(l,h) for(int i=(l);i<=(h);++i) #define FOR3(h,l) for(int i=(h);i>=(l);--i) using namespace std; typedef vector<int> VI; typedef vector<string> VS; typedef vector<double> VD; typedef long long LL; typedef pair<int,int> PII; #define PI acos((double)-1) #define E exp(double(1)) #define K 1000000+9 int h[K],tol=0; int d[K],vis[K],c[K],flag; struct node { int to,next,w; }e[K]; void init(int n) { memset(h,-1,sizeof(h)); memset(e,0,sizeof(e)); memset(d,0x3f,sizeof(d)); memset(c,0,sizeof(c)); memset(vis,0,sizeof(vis)); tol=0; flag=0; d[1]=0; } void add(int u,int v,int w) { e[tol].to=v; e[tol].next=h[u]; e[tol].w=w; h[u]=tol++; } void dfs(int s) { vis[s]=1; for(int i=h[s];~i;i=e[i].next) { int v=e[i].to; if(d[v]>d[s]+e[i].w) { d[v]=d[s]+e[i].w; if(vis[v]) { flag=1; return ; } dfs(v); } } vis[s]=0; } int main(void) { int t; cin>>t; while(t--) { int n,m,q,u,v,w; cin>>n>>m>>q; init(n); for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); add(v,u,w); } for(int i=1;i<=q;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,-w); } dfs(1); if(flag) printf("YES "); else printf("NO "); } return 0; }
poj3259 Wormholes