模板 - SPFA

SPFA可以用来判断负环或者计算带负权的最短路。

其实带负权的最短路可以用带势Dijkstra计算……

所以SPFA基本就拿来判负环了……

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

namespace SPFA{

    const int MAXN=5010;

    const int MAXM=10010;

    const int INF=0x3f3f3f3f;

    int tol;

    int head[MAXN];

    struct Edge{

        int to,next,cost;

    }edge[MAXM];

    void init(){

        tol=1;

        memset(head,-1,sizeof(head));

    }

    void add_edge(int u,int v,int cost){

        edge[tol].to=v;

        edge[tol].cost=cost;

        edge[tol].next=head[u];

        head[u]=tol++;

    }

    bool vis[MAXN];

    int cnt[MAXN];

    int dist[MAXN];

    bool spfa(int s,int n){

        memset(vis,0,sizeof(vis));

        memset(cnt,0,sizeof(cnt));

        memset(dist,0x3f,sizeof(dist));

        queue<int>que;

        while(!que.empty())que.pop();

        que.push(s);

        vis[s]=true;

        cnt[s]=1;

        dist[s]=0;

        while(!que.empty()){

            int u=que.front();

            que.pop();

            vis[u]=false;

            for(int i=head[u];i!=-1;i=edge[i].next){

                int v=edge[i].to;

                if(dist[v]>dist[u]+edge[i].cost){

                    dist[v]=dist[u]+edge[i].cost;

                    if(!vis[v]){

                        vis[v]=true;

                        que.push(v);

                        if(++cnt[v]>n){

                            return false;

                        }

                    }

                }

            }

        }

        return true;

    }

}

using namespace SPFA;