spfa判断负环模板题
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 510,M = 5210;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
int cnt[N];
int q[N];
void add(int a, int b, int c)
{
e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int n,m1,m2;
bool spfa(){
memset(cnt,0,sizeof(cnt));
memset(st,0,sizeof(st));
memset(dist,0x3f,sizeof(dist));
int hh = 0,tt = 0;
for(int i=1;i<=n;i++){
q[tt++] = i;
st[i] = true;
}
while(hh != tt){
int t = q[hh++];
if(hh == N) hh = 0;
st[t] = false;
for(int i=h[t];i!=-1;i=ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1;
if(cnt[j] >= n) return true;
if(!st[j]){
q[tt++] = j;
if(tt == N) tt = 0;
st[j] = true;
}
}
}
}
return false;
}
int main()
{
int T;
scanf("%d",&T);
while(T -- ){
memset(h, -1, sizeof h);
idx = 0;
scanf("%d %d %d",&n,&m1,&m2);
while(m1 -- ){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
while(m2 -- ){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
add(a,b,-c);
}
if(spfa()) puts("YES");
else puts("NO");
}
return 0;
}