题意：给出n个点，m条正权的边，w条负权的边，问是否存在负环
因为Bellman_ford最多松弛n-1次， 因为从起点1终点n最多经过n-2个点，即最多松弛n-1次，如果第n次松弛还能成功的话，则说明存在有负环
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int maxn=10005; 16 int d[maxn]; 17 int flag; 18 int nodenum,edgenum,ecnt; 19 20 struct Edge{ 21 int u,v,cost; 22 } e[maxn]; 23 24 int Bellman_ford(){ 25 for(int i=1;i<=nodenum;i++) d[i]=INF; 26 d[1]=0; 27 28 for(int i=1;i<nodenum;i++){ 29 for(int j=1;j<=ecnt;j++){ 30 if(d[e[j].v]>d[e[j].u]+e[j].cost) 31 d[e[j].v]=d[e[j].u]+e[j].cost; 32 } 33 } 34 35 flag=1; 36 for(int i=1;i<=ecnt;i++){ 37 if(d[e[i].v]>d[e[i].u]+e[i].cost){ 38 flag=0; 39 break; 40 } 41 } 42 return flag; 43 } 44 45 void addedges(int a,int b,int c){ 46 e[++ecnt].u=a; 47 e[ecnt].v=b; 48 e[ecnt].cost=c; 49 } 50 51 int main(){ 52 int m,w,ncase; 53 int a,b,c; 54 scanf("%d",&ncase); 55 while(ncase--){ 56 ecnt=0; 57 scanf("%d %d %d",&nodenum,&m,&w); 58 while(m--){ 59 scanf("%d %d %d",&a,&b,&c); 60 addedges(a,b,c); 61 addedges(b,a,c); 62 } 63 while(w--){ 64 scanf("%d %d %d",&a,&b,&c); 65 c=-c; 66 addedges(a,b,c); 67 } 68 if(Bellman_ford()) printf("NO "); 69 else printf("YES "); 70 } 71 return 0; 72 }