SPFA代码参考P1023 题解

因为SPFA中的点有可能会重复入队，没有vis标记。如果有负环的话，SPFA肯定会陷入死循环。
那么只需要略作修改，统计一下入队次数就可以。

// 只给出部分代码，其他见P1023题解
queue<int> q;
int cnt[MAXN];
bool SPFA(int s){ // 有负环返回true
    for(int i=0; i<=n; i++) dis[i] = INF; // 初始化为无穷大
    dis[s] = 0;
    vis[s] = true; // 标记该点
        cnt[s]++;
    q.push(s);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=h[u]; i; i=nxt[i]){
            int v=to[i];
            if(dis[v]>dis[u]+val[i]){ // 如果可以松弛
                dis[v]=dis[u]+val[i];
                q.push(v); // 松弛后入队
                                cnt[v]++;
                                if (cnt[v] > n) return true;
                                // 找到入队次数大于n的点，存在可到达的负环
            }
        }
    }
    return false;
}