spfa板子

spfa板子

Heap+Dijkstra都会写，突然发现spfa不会写了……

inq[]记录是否已在队列中

inline void spfa(int s){
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        inq[u]=0;
        for(register int i=head[u];i;i=nxt[i]){
            int v=vv[i];
            if(dis[v]<dis[u]+ww[i]){
                dis[v]=dis[u]+ww[i];
                if(!inq[v]) inq[v]=1,q.push(v);
            }
        }
    }
}

判负环

图中无负环时，一个点最多只能被其他点松弛(n-1)次

inline bool spfa(int s){
    q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        inq[u]=0;
        for(register int i=head[u];i;i=nxt[i]){
            int v=vv[i];
            if(dis[v]<dis[u]+ww[i]){
                dis[v]=dis[u]+ww[i];
                cnt[v]=cnt[u]+1;
                if(cnt[v]>=n) return 0;
                if(!inq[v]) inq[v]=1,q.push(v);
            }
        }
    }
    return 1;
}

更高效的dfs版spfa判负环