SPFA找负环(DFS) luogu3385

SPFA找负环的基本思路就是如果一个点被访问两次说明成环，如果第二次访问时所用路径比第一次短说明可以通过一直跑这个圈将权值减为负无穷，存在负环

有bfs和dfs两种写法，看了一些博客，在bfs和dfs间选择了dfs，因为我认为如果整个图是一个环，从一个点开始，在此点对面的一条边为非常大的负权边，这种情况bfs会非常慢

另外还有一个优化，dis初始化为0而非INF，这样舍弃了dis保存最短路径的特性，保证了每次dfs总是从负权边开始，尽管这道题上这个优化并没有什么效果……

// luogu 3385 
#include<bits/stdc++.h>
using namespace std;
inline int read(){
    int x = 0,f= 1; char ch = getchar();
    while(ch<'0' || ch>'9') {if(ch == '-') f=-1;ch = getchar();}
    while(ch>='0'&&ch<='9') {x = x*10+ch-'0';ch = getchar();}
    return x*f;
}
int T,n,m,st,ed,le,flag;
struct EDGE{
    int to,next,len;
    EDGE(){}
    EDGE(int a,int b,int c){
        to = a, next = b, len = c;
    }
}e[400100];
int head[200100],dis[200100],cnt,vis[200100];
void init(){
    memset(head,0,sizeof(head));
    memset(dis,0,sizeof(dis));
    memset(vis,0,sizeof(vis));
    cnt = 0;
    flag = 0;
}
void add(int u, int v, int w){
    e[++cnt] = EDGE(v,head[u],w);
    head[u] = cnt;
}
void spfa_dfs(int st){
    //cout<<st<<endl;
    if(flag) return;
    vis[st] = 1;
    for(int i = head[st];i;i = e[i].next){
        int to = e[i].to;
        if(dis[st]+e[i].len<dis[to]){
            dis[to] = dis[st]+e[i].len;
            if(vis[to]){
                flag = 1;
                return;
            }
            else spfa_dfs(to);    
        }
    }
    vis[st] = 0;
}
int main(){
    T = read();
    while(T--){
        init();
        n = read(); m = read();
        for(int i = 0;i<m;i++){
            st = read(); ed = read(); le = read();
            add(st,ed,le);
            if(le>=0) add(ed,st,le);
        }
        for(int i = 1;i<=n;i++){
            if(flag) break;
            spfa_dfs(i);
        }
        if(flag) printf("YE5
");
        else printf("N0
");
    }
    return 0;
}