1 solutions

  • 0
    @ 2024-4-2 14:33:32
    //算法分析:记录某个点的某条路径上的点的数目,如果某条路径上的点的数目超过了n个,那么根据抽屉原理,一定出现了负环 
    
    #include<bits/stdc++.h>
    using namespace std;
    const int N=2010,M=10010;
    int h[N],e[M],ne[M],w[M],idx;
    bool st[N];
    int n,m;
    int dist[N],cnt[N];
    void add(int a,int b,int c)
    {
        e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
    }
    bool spfa()
    {
        queue<int> q;
        memset(dist,0,sizeof dist);
        for(int i=1;i<=n;i++) //所有点入队 
        {
            q.push(i);
            st[i]=1;
        }
        while(q.size())
        {
            int t=q.front();
            q.pop();
            st[t]=false;
            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) //从某个点到当前点的入队次数超过了n(根据抽屉原理,一定又换) 
                    {
                        return true;
                    }
                    if(!st[j]) //进入队列之中 
                    {
                        st[j]=1;
                        q.push(j);
                    }
                }
            }
        }
        return false;
    }
    int main()
    {
        cin>>n>>m;
        memset(h,-1,sizeof h);
        for(int i=1;i<=m;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            add(a,b,c);
        }
        if(spfa()) cout<<"Yes";
        else
        {
            cout<<"No";
        }
        return 0;
    }
    
    • 1

    Information

    ID
    1368
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    10
    Tags
    (None)
    # Submissions
    5
    Accepted
    3
    Uploaded By