题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1715
SPFA判负权环
我的模板库
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
const int maxe(3000);
const int maxv(800);
using namespace std;
int ecnt,n,dis[maxv],sum[maxv];
bool vis[maxv];
int head[maxv];
struct edge
{int next,to,dis;
}ed[maxe];
queue<int> q;
void add_edge(int from,int to,int dis)
{ed[++ecnt].next=head[from];ed[ecnt].to=to;ed[ecnt].dis=dis;head[from]=ecnt;
}
void init()
{int m,w;scanf("%d%d%d",&n,&m,&w);int a1,a2,a3;for(int i=1;i<=m;i++){scanf("%d%d%d",&a1,&a2,&a3);add_edge(a1,a2,a3);add_edge(a2,a1,a3);}for(int i=1;i<=w;i++){scanf("%d%d%d",&a1,&a2,&a3);add_edge(a1,a2,-a3);
// add_edge(a2,a1,-a3);}return;
}
bool SPFA()
{memset(vis,0,sizeof(vis));memset(dis,0x3f,sizeof(dis));memset(sum,0,sizeof(sum));dis[1]=0;q.push(1);vis[1]=1; while(!q.empty()){int t=q.front();vis[t]=0;q.pop();for(int i=head[t];i;i=ed[i].next){int et=ed[i].to;int d=ed[i].dis;if(d+dis[t]<dis[et]){if(++sum[et]>n) return false;dis[et]=d+dis[t];if(!vis[et]){q.push(et);vis[et]=1;}}}}return 1;
}
int main()
{ int tt;scanf("%d",&tt);for(int i=1;i<=tt;i++){init();if(SPFA()) printf("NO\n");else printf("YES\n"); } return 0;
}