bellman-ford算法

#include<cstdio>
#include<cstring>
using namespace std;
const int N=5+2e3,M= 5 + 6e3;
class Edge{
public:
    int u,v,w;
}edge[M];
int dis[N];
int cnt=0;
int n;
void add_edge(int u,int v,int w){
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt++].w=w;
}
bool bellman_ford(){
    dis[1]=1;
    for(int i=0;i<n-1;++i){
        bool flag=false;
        for(int j=0;j<cnt;++j){
            int u=edge[j].u,v=edge[j].v,w=edge[j].w;
            if(dis[u]>=0x3f3f3f3f)continue;
            w+=dis[u];
            if(w<dis[v]){
                dis[v]=w;
                flag=true;
            }
        }
        if(!flag)return false;
    }
    for(int j=0;j<cnt;++j){
        int u=edge[j].u,v=edge[j].v,w=edge[j].w;
        if(dis[u]>=0x3f3f3f3f)continue;
        w+=dis[u];
        if(w<dis[v])return true;
    }
    return false;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        int m;
        scanf("%d%d",&n,&m);
        memset(dis,0x3f,sizeof(dis));
        cnt=0;
        while(m--){
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            add_edge(u,v,w);
            if(w>=0)add_edge(v,u,w);
        }
        if(bellman_ford())printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}