负环

Bellman-Ford

const int inf=0x3f3f3f3f,maxn=110,maxm=10010;
int n,m,dis[maxn];

struct Edge{
    int u,v,w;
}edge[maxm];

bool Bellman_Ford(){
    memset(dis,inf,sizeof(dis));
    dis[1]=0;
    int check;
    for(int i=1;i<=n;i++){
        check=0;
        for(int j=1;j<=m;j++){
            int u=edge[j].u,v=edge[j].v,w=edge[j].w;
            if(dis[v]>dis[u]+w){
                dis[v]=min(dis[v],dis[u]+w);
                if(i==n) return true;
                check=1;
            }
        }
        if(!check) break;
    }
    return false;
}

SPFA

const int maxn=1010,inf=0x3f3f3f3f;
int n,inq[maxn],cnt[maxn],dis[maxn];

bool spfa(int s){
    for(int i=1;i<=n;i++){
        dis[i]=(i==s)?0:inf;
        inq[i]=(i==s)?1:0;
        cnt[i]=(i==s)?1:0;
    }
    queue<int> q;
    q.push(s);
    while(!q.empty()){
        int p=q.front();
        q.pop();
        inq[p]=0;
        for(int i=head[p];~i;i=nxt[i]){
            int v=to[i],w=weight[i];
            if(dis[v]>dis[p]+w){
                dis[v]=dis[p]+w;
                cnt[v]++;
                if(cnt[v]>=n) return true;
                if(!inq[v]){
                    inq[v]=1;
                    q.push(v);
                }
            }
        }
    }
    return false;
}