负环（SPFA）

问图中是否有负环，一条回路，权值和为负数。

思路：SPFA算法求最短路的时候，每个节点最多入队n-1次，如果多了，那就是存在负环。

注释：是最短路算法，但是不建议拿来求最短路，复杂度一般都是N^2，仅适用负环问题

最短路（负权）SPFA，或判负环（复杂度一般N^2）
const int MAX=INT_MAX>>1;//考虑LONG_LONG_MAX
const int N=2e3+5;//最多节点数量

int n;//实际节点数量
int dist[N],cnt[N];
queue<int>q;
bitset<N>vis;
vector<pair<int,int>>e[N];//e[i]={w,j},i节点到j节点距离w

void spfa(int s){//s点出发的最短路
    for(int i=1;i<=n;++i)dist[i]=MAX;
    dist[s]=0;

    q.push(s);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        vis[now]=false;

        for(auto i:e[now]){
            int nxt=i.second,tonxt=i.first;
            if(dist[now]+tonxt<dist[nxt]){
                dist[nxt]=dist[now]+tonxt;
                if(!vis[nxt]){
                    vis[nxt]=true;
                    q.push(nxt);
                    //此处cnt数组和判断删掉就是正常的SPFA
                    //还有下面的cout<<no;
                    if(++cnt[nxt]>=n){//判断入队次数
                        cout<<"YES"<<endl;//存在负环
                        return;
                    }
                }
            }
        }
    }}
    cout<<"NO"<<endl;
    
最短路（正权）Dj
const int N=1e5+5;//最多节点
struct{
    int MAX=INT_MAX>>1;//最大值,是否需要改成long long自行观察
    
    int n;//dj实际节点
    int dist[N];
    bitset<N>vis;
    vector<pair<int,int>>e[N];//e[i]={w,j},点i到j需要距离w
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q;
    
    void dijkstra(int s){//从s点出发 dj
        for(int i=1;i<=n;++i)
            dist[i]=MAX;
        dist[s]=0;
        
        q.push({0,s});
        while(!q.empty()){
        int now=q.top().second;
        int nowDis=q.top().first;
        q.pop();
 
        if(vis[now])continue;
        vis[now]=true;
        for(auto i:e[now]){
            int toNextLength=i.first;
            int nxt=i.second;
 
            if(dist[nxt]>dist[now]+toNextLength){
                dist[nxt]=dist[now]+toNextLength;
                if(!vis[nxt]){
                    q.push({dist[nxt],nxt});
                }
            }
          }
        }
    }
}dj;