SPFA模板（vector版本）

浅浅的花香味﹌ 2022-05-06 16:00 215阅读 0赞

## 入门参考[https://www.cnblogs.com/bofengyu/p/5004398.html][https_www.cnblogs.com_bofengyu_p_5004398.html]。 ##

#pragma comment(linker, "/STACK:102400000,102400000")
    #include<unordered_map>
    #include<unordered_set>
    #include<algorithm>
    #include<iostream>
    #include<fstream>
    #include<complex>
    #include<cstdlib>
    #include<cstring>
    #include<cassert>
    #include<iomanip>
    #include<string>
    #include<cstdio>
    #include<bitset>
    #include<vector>
    #include<cctype>
    #include<cmath>
    #include<ctime>
    #include<stack>
    #include<queue>
    #include<deque>
    #include<list>
    #include<set>
    #include<map>
    using namespace std;
    #define pt(a) cout<<a<<endl
    #define debug test
    #define mst(ss,b) memset((ss),(b),sizeof(ss))
    #define rep(i,a,n) for (int i=a;i<=n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pii pair<int,int>
    #define fi first
    #define se second
    #define ll long long
    #define ull unsigned long long
    #define pb push_back
    #define mp make_pair
    #define inf 0x3f3f3f3f
    #define eps 1e-10
    #define PI acos(-1.0)
    const ll mod = 1e9+7;
    const int N = 1e6+10;
    
    struct Edge{
        int v,cost;
    };
    vector<Edge>E[N];
    
    bool vis[N];///在队列标志
    int cnt[N];///每个点的入队列次数
    int d[N];
    
    bool spfa(int s,int n){///判断是否有负环
        mst(vis,false);
        mst(d,0);
        vis[s]=true;
        d[s]=0;
        queue<int>q;
        q.push(s);
        mst(cnt,0);
        cnt[s]=1;
        while(!q.empty()){
            int u=q.front();
            q.pop();
            vis[u]=false;
            for(int i=0; i<E[u].size(); i++){
                int v=E[u][i].v;
                if(d[v]>d[u]+E[u][i].cost){
                    d[v]=d[u]+E[u][i].cost;
                    if(!vis[v]){
                        vis[v]=true;
                        q.push(v);
                        if(++cnt[v]>n)return false;//cnt[i] 为入队列次数，用来判定是否存在负环回路
                    }
                }
            }
        }
        return true;
    }
    
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
        return 0;
    }

[https_www.cnblogs.com_bofengyu_p_5004398.html]: https://www.cnblogs.com/bofengyu/p/5004398.html