洛谷P3385-【模板】负环 (SPFA)

传送门

思路：SPFA找负环，此题数据非常强大。根据信息学奥赛一本通·提高篇中所述，DFS-SPFA找负环速度很快，实际上并不是这样，直接TLE。

之前用的普通BFS-SPFA模版也一样TLE，在题解区发现有一种新写法，更新时用cnt[v]=c[u]+1取代cnt[v]++，速度快了一倍左右，正确性有待考证，做了几道题目到目前为止没有发现问题。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

const int MAXN=2005;
const int INF=0x3f3f3f3f;
int n,m;
struct Edge
{
    int v;
    int cost;
    Edge(int _v=0,int _cost=0):v(_v),cost(_cost) {}
};
vector<Edge>E[MAXN];
void addedge(int u,int v,int w)
{
    E[u].push_back(Edge(v,w));
}
bool vis[MAXN];//在队列标志
int cnt[MAXN];//每个点的入队列次数
int dist[MAXN];
bool SPFA()
{
    queue<int>que;
    while(!que.empty())que.pop();
    for(int i=1; i<=n; i++)
    {
        vis[i]=false;
        dist[i]=INF;
        cnt[i]=0;
    }
    que.push(1);
    cnt[1]=1;
    dist[1]=0;
    while(!que.empty())
    {
        int u=que.front();
        que.pop();
        vis[u]=false;
        for(int i=0; i<E[u].size(); i++)
        {
            int v=E[u][i].v;
            if(dist[v]>dist[u]+E[u][i].cost)
            {
                dist[v]=dist[u]+E[u][i].cost;
                if(!vis[v])
                {
                    cnt[v]=cnt[u]+1;
                    //cnt[v]++;
                    if(cnt[v]>n)return true;
                    vis[v]=true;
                    que.push(v);
                }
            }
        }
    }
    return false;
}
int main()
{
    int ww;
    scanf("%d",&ww);
    while (ww--)
    {
        scanf("%d%d",&n,&m);
        for (int i=1; i<=n; i++)
            E[i].clear();
        for (int i=0; i<m; i++)
        {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            addedge(a,b,c);
            if (c>=0)
                addedge(b,a,c);
        }
        bool flag=SPFA();
        if (flag)
            printf("YE5\n");
        else
            printf("N0\n");
    }
    return 0;
}