SPFA模板题判断是否有负环
题目链接：POJ-3259
AC代码：
#include<iostream> #include<cstring> #include<cstdio> #include<queue> using namespace std; const int N=1e3+10; const int INF=0x3f3f3f3f; #define MM(x,y) memset(x,y,sizeof(x)) struct Node { int to; int next; int cst; }; struct Node edge[N*N]; int cnt,n,w,m; int head[N]; int d[N]; bool vis[N]; int cont[N]; queue<int>Q; void add(int u,int v,int cost) { edge[cnt].to=v; edge[cnt].cst=cost; edge[cnt].next=head[u]; head[u]=cnt++; } void init() { for(int i=0;i<N;i++) { head[i]=-1; d[i]=INF; cont[i]=0; vis[i]=0; } cnt=0; while(!Q.empty()) { Q.pop(); } } bool spfa(int s,int n) { d[s]=0; Q.push(s); vis[s]=1; while(!Q.empty()) { int u=Q.front(); Q.pop(); vis[u]=0; for(int i=head[u];~i;i=edge[i].next) { int v=edge[i].to; if(d[v]>d[u]+edge[i].cst) { d[v]=d[u]+edge[i].cst; if(!vis[v]) { Q.push(v); vis[v]=1; cont[v]++; if(cont[v]>=n) return true; } } } } return false; } int main() { int tcase,i,j,u,v,cost; scanf("%d",&tcase); while(tcase--) { init(); scanf("%d%d%d",&n,&m,&w); for(i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&cost); add(u,v,cost); add(v,u,cost); } for(i=1;i<=w;i++) { scanf("%d%d%d",&u,&v,&cost); add(u,v,-cost); } if(spfa(1,n)) { printf("YES\n"); } else { printf("NO\n"); } } return 0; }