@[一只萌新](/space/show?uid=103655) My AC Code
```cpp
#include<bits/stdc++.h>
using namespace std;
const int maxn=100001;
int tot,pre[maxn],now[maxn],son[maxn],val[maxn],dep[maxn];
void ins(int x,int y,int z) {
pre[++tot]=now[x];
now[x]=tot;
son[tot]=y;
val[tot]=z;
}
int T,n,s1,s2,s,e,v;
int dis[maxn];
bool flag,vis[maxn];
void SPFA(int u) {
vis[u]=true;
for(int p=now[u]; p; p=pre[p]) {
int s=son[p],v=val[p];
if(dis[s]>dis[u]+v) {
dis[s]=dis[u]+v;
dep[s]=dep[u]+1;
if(dep[s]>n) {
flag=true;
break;
}
SPFA(s);
}
}
vis[u]=false;
}
void prep() {
tot=0,flag=false;
memset(pre,0,sizeof(tot));
memset(now,0,sizeof(now));
memset(son,0,sizeof(son));
memset(val,0,sizeof(val));
memset(dep,0,sizeof(dep));
memset(dis,0x3f,sizeof(dis));
memset(vis,false,sizeof(vis));
}
void init() {
scanf("%d%d%d",&n,&s1,&s2);
for(int i=1; i<=s1; i++) {
scanf("%d%d%d",&s,&e,&v);
ins(s,e,v),ins(e,s,v);
}
for(int i=1; i<=s2; i++) {
scanf("%d%d%d",&s,&e,&v);
ins(s,e,-v);
}
}
void solve() {
for(int i=1; i<=n; i++) {
SPFA(i);
if(flag)break;
}
puts(flag?"YES":"NO");
}
int main() {
scanf("%d",&T);
while(T--) {
prep();
init();
solve();
}
return 0;
}
```
by liao @ 2019-02-11 23:24:54
@[liao](/space/show?uid=106791) 我知道，spfa啊，但是我之前的dfs为什么不可以呢想不通啊
by 一只萌新 @ 2019-02-24 19:20:01