c/c++语言开发共享<题解>洛谷P3385 【模板】负环

#include<bits/stdc++.h>万能头，懒得打很多头文件  using namespace std;  //数据是骗人的，要开大..  const int maxn=50001;  //基本的变量或者数组都是：  queue<int > q;  bool visited[maxn];  int head[maxn],cnt,js[maxn],dis[maxn];  struct ppap {      int next,to,dis;  } edge[maxn];  int t,n,m;  //快读部分  int read() {      bool f=0;      char ch;      int x=0;      ch=getchar();      while(ch>'9'||ch<'0') {          if(ch=='-')              f=!f;          ch=getchar();      }      while(ch<='9'&&ch>='0') {          x=x*10+ch-'0';          ch=getchar();      }      return !f?x:-x;  }  //链式前向星添边  void add(int from,int to,int dis) {      edge[++cnt].next=head[from];      head[from]=cnt;      edge[cnt].to=to;      edge[cnt].dis=dis;  }  //和常见spfa一样，在其中判断条件即可  bool spfa() {      q.push(1);      visited[1]=1;      dis[1]=0;      js[1]=1;      while(!q.empty()) {          int u=q.front();          q.pop();          visited[u]=0;          for(int i=head[u]; i; i=edge[i].next) {              int v=edge[i].to;              if(dis[v]>dis[u]+edge[i].dis) {                  dis[v]=dis[u]+edge[i].dis;                  if(visited[v]==0) {                      js[v]=js[u]+1;                      if(js[v]>n) return true;                      visited[v]=1;                      q.push(v);                  }              }          }      }      return false;  }    int main() {      t=read();      while(t--) {          n=read(),m=read();          memset(head,0,sizeof head);          memset(js,0,sizeof js);          memset(edge,0,sizeof edge);          memset(dis,0x3f,sizeof dis);          memset(visited,0,sizeof visited);          //初始化          for(int i=1,a,b,w; i<=m; i++) {              a=read(),b=read(),w=read();              add(a,b,w);              if(w>=0)                  add(b,a,w);          }          if(spfa()) cout<<"ye5"<<"n";          else cout<<"n0"<<"n";      }      return 0;//平淡的结束  }