SPFA.cpp

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const int MAXM = 6005;
const int MAXQ = 4000005;
vector<int>head(MAXN,0);
vector<int>to(MAXM,0);
vector<int>nextn(MAXM,0);
vector<int>weight(MAXM,0);
vector<int>dist(MAXN,INT_MAX);
vector<bool>enter(MAXQ,false);
vector<int>cnt(MAXN,0);
vector<int>queue(MAXQ);
int cnt;
int main()
{
    cnt = 1;
    int l,r;
    l = r = 0;
    queue[r++] = 1;
    dist[1] = 0;
    cnt[1] = 1;
    enter[1] = true;
    while(l<r)
    {
        int tmp = queue[l++];
        enter[tmp] = false;
        for(int ei = head[tmp];ei != 0;ei = nextn[ei])
        {
            int v = to[ei];
            int w = weight[ei];
            if(dist[tmp]+w <dist[v])
            {
                dist[v] = dist[tmp]+w;
                if(++cnt[v]>n-1)
                return true;
                queue[r++] = v;
                enter[v] = true;
            }
        }
    }
}
void addedge(int i,int j,int k)
{
    nextn[cnt] = head[i];
    to[cnt] = j;
    weight[cnt] = k;
    head[i] = cnt++;
}