【luogu3385】【模板】负环 [spfa判负环]

P2850 [USACO06DEC]虫洞Wormholes 这题和这个是一样的只是输入时不一样

看学长的模板然后自己写一个用双档队列优化的超时了QAQ 然后回归学长的模板

就是判断一个点它是否经过了大于n次如果大于了n次那就说明有负环 (大概是这个意思)

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<stack>
 7 #include<algorithm>
 8 using namespace std;
 9 #define ll long long
10 #define rg register
11 const int N=2000+5,M=3000+5,inf=0x3f3f3f3f;
12 int n,m;
13 template <class t>void rd(t &x)
14 {
15     x=0;int w=0;char ch=0;
16     while(!isdigit(ch)) w|=ch=='-',ch=getchar();
17     while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
18     x=w?-x:x;
19 }
20 
21 int tot,head[N];
22 struct edge{int v,nxt,w;}e[M<<1];
23 void add(int u,int v,int w){
24     e[++tot].v=v,e[tot].nxt=head[u],e[tot].w=w,head[u]=tot;
25 }
26 
27 int dis[N],len[N];
28 bool vis[N];
29 queue<int>q;
30 bool spfa(int s)
31 {
32     for(rg int i=1;i<=n;++i) dis[i]=inf,vis[i]=0,len[i]=-1;
33     dis[s]=0,vis[s]=1,len[s]=0;
34     while(!q.empty()) q.pop();
35     q.push(s);
36     while(!q.empty())
37     {
38         int u=q.front();
39         q.pop(),vis[u]=0;
40         if(len[u]>=n) return 1;
41         for(int i=head[u];i;i=e[i].nxt)
42         {
43             int v=e[i].v,w=e[i].w;
44             if(dis[v]>dis[u]+w)
45             {
46                 dis[v]=dis[u]+w,len[v]=len[u]+1;
47                 if(!vis[v]) vis[v]=1,q.push(v);
48             }
49         }
50     }
51     return 0;
52 }
53 
54 void clean()
55 {
56 //    memset(head,0,sizeof(head));
57     tot=0;
58     for(rg int i=1;i<=n;++i) head[i]=0;
59 }
60 
61 int main()
62 {
63     freopen("in.txt","r",stdin);
64     //freopen("out.txt","w",stdout);
65     int T;rd(T);
66     while(T--)
67     {
68         rd(n),rd(m);
69         clean();
70         for(rg int i=1;i<=m;++i)
71         {
72             int u,v,w;rd(u),rd(v),rd(w);
73             add(u,v,w);
74             if(w>=0) add(v,u,w);
75         }
76         if(spfa(1))puts("YE5");
77         else puts("N0");
78     }
79     return 0;
80 }