void SPFA(){
    q.push(1);
    flag[1]=true;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        flag[u]=false;
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i].first,w=g[u][i].second;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                if(!flag[v]){
                    q.push(v);
                    flag[v]=true;
                }
            }
        }
    }
}

判负环

void SPFA(int s){
    memset(flag,false,sizeof(flag));
    memset(d,127,sizeof(d));
    memset(cnt,0,sizeof(cnt));
    while(!q.empty())q.pop();
    d[s]=0;
    cnt[s]++;
    q.push(s);
    flag[s]=true;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        flag[u]=false;
        for(int i=0;i<g[u].size();i++){
            int v=g[u][i].first,w=g[u][i].second;
            if(d[u]+w<d[v]){
                d[v]=d[u]+w;
                if(!flag[v]){
                    q.push(v);
                    flag[v]=true;
                    cnt[v]++;
                    if(cnt[v]==n){
                        f=true;
                        cout<<"-1";
                        exit(0);
                    }
                }        
            }
        }
    }
}