题目描述

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=510,M=5210;
int h[N],e[M],ne[M],w[M],idx;
int dist[N],cnt[N];
int st[N];
int n,m,k;
void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int spfa()
{
    memset(dist, 0, sizeof dist);
    memset(st,0,sizeof st);
    memset(cnt,0,sizeof cnt);

    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        st[i]=1;
        q.push(i);
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=0;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];

            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return 1;
                if(!st[j])
                {
                    st[j]=1;
                    q.push(j);
                }

            }

        }

    }
    return 0;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        cin >> n >> m >> k;
        memset(h, -1, sizeof h);
        idx = 0;
        for (int i = 0; i < m; i ++ )
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c), add(b, a, c);
        }
        for (int i = 0; i < k; i ++ )
        {
            //虫洞 回到t秒前  时间time-t秒
            // 单向负边
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, -c);
        }

        if (spfa()==1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }

    return 0;


}

二刷，spfa求负环要注意：

1. 记得维护cnt数组，当cnt>=n时return
2. 做spfa时，不要单独设置dist[s]=0,每个点入队，st设置为1

三刷，刚开始还是没写出来，需要复习

需要注意以下几点：
1. spfa求负环，刚开始要把所有点入队，并同时把st设置为1
2. 维护一个cnt数组，保存到这个点的最短路经过的点的数量
3. ！！很重要！！结束条件为：cnt[j]>n

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=100010;
int n,m,k;
int T;

int h[N],e[N],ne[N],w[N],idx,st[N];
int dist[N];
int cnt[N];

void add(int a,int b,int c)
{
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}

int spfa()
{
    memset(dist,0,sizeof dist);
    memset(cnt,0,sizeof cnt);
    queue<int> q;

    for(int i=1;i<=n;i++)
    {
        q.push(i);
        st[i]=1;
    }
    int flag=0;
    while(q.size())
    {
        int t=q.front();
        q.pop();
        st[t]=0;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];

            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return 1;
                if(!st[j])
                {
                    q.push(j);
                }
            }
        }
    }

    return 0;
}

int main()
{
    cin>>T;
    while(T--)
    {
        memset(st,0,sizeof st);
        memset(h,-1,sizeof h);
        memset(e,0,sizeof e);
        memset(w,0,sizeof w);
        memset(ne,0,sizeof ne);
        idx=0;

        cin>>n>>m>>k;
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
            add(b,a,c);
        }
        for(int i=1;i<=k;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,-c);
        }
        if(spfa()==1) cout<<"YES";
        else cout<<"NO";
        cout<<endl;

    }
    return 0;
}

2024/1/3

求负环用spfa，先复习spfa
重点是要维护一个cnt数组：记录当前点的最短路经过的点的数量(或者是当前点的最短路已经经过的边数)
每次更新当前点的dist时，用前一个点的cnt+1

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

const int N=200100;

int e[N], ne[N], w[N], h[N], idx;
int st[N];
int dist[N], cnt[N];
int n,m,k,T;

void add(int a,int b,int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

int spfa()
{
    queue<int> q;

    for(int i=1;i<=n;i++)
    {
        st[i] = 1;
        q.push(i);
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();

        st[t] = 0;

        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];

            if(cnt[j]>=n)
            {
                return 0;
            }

            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;
                if(!st[j])
                {
                    q.push(j);
                }
            }


        }

    }

    return 1;

}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        memset(h, -1, sizeof(h));
        memset(cnt, 0,sizeof(cnt));
        // memset(dist, 0x3f, sizeof(dist));

        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
            add(b,a,c);
        }

        for(int i=1;i<=k;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,-c);
        }

        int result = spfa();
        if(result == 1)
        {
            cout<<"NO"<<endl;
        }
        else
        {
            cout<<"YES"<<endl;
        }




    }

    return 0;
}