洛谷 P3387 题解

题面

裸跑一遍SPFA，统计每个点的入队次数；

如果该点的入队次数>=总点数，那么该点便是一个负环上的点；

重点！！！：

1.不是“YES”，是“YE5”；

2.不是“NO”，是“N0”；(是零)；

3.多测不清空，爆零两行泪；

#include <bits/stdc++.h>

#pragma GCC optmize(2)

using namespace std;

int t;

int n,m;

struct littlestar{

    int to;

    int nxt;

    int w;

}star[];

int head[],cnt;

void add(int u,int v,int w)

{

    star[++cnt].to=v;

    star[cnt].nxt=head[u];

    star[cnt].w=w;

    head[u]=cnt;

}

queue<int> q;

int dis[],vis[];

int num[];

void SPFA()

{

    memset(num,,sizeof(num));

    memset(vis,,sizeof(vis));

    memset(dis,0x3f,sizeof(dis));

    while(q.size()) q.pop();

    q.push();

    vis[]=;

    dis[]=;

    while(q.size()){

        int u=q.front();

        q.pop();

        vis[u]=;

        for(int i=head[u];i;i=star[i].nxt){

            int v=star[i].to;

            if(dis[v]>dis[u]+star[i].w){

                dis[v]=dis[u]+star[i].w;

                if(!vis[v]){

                    vis[v]=;

                    q.push(v);

                    ++num[v];

                    if(num[u]>=n){

                        cout<<"YE5"<<endl;

                        return;

                    }

                }

            }

        }

    }

    cout<<"N0"<<endl;

    return;

}

int main ()

{

    cin>>t;

    while(t--){

        memset(star,,sizeof(star));

        memset(head,,sizeof(head));

        scanf("%d%d",&n,&m);

        for(register int i=;i<=m;i++){

            int u,v,w;

            scanf("%d%d%d",&u,&v,&w);

            add(u,v,w);

            if(w>=) add(v,u,w);

        }

        SPFA();

    }

    return ;

}