poj 3259 最短路径spfa判断是否有负环

谁借莪１个温暖的怀抱￠ 2022-08-03 08:43 125阅读 0赞

只要有负环就可以在里面循环好多次，然后攒够了足够的时间就可以随便找一条路回家啦

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    
    struct st
    {
        int to,cost;
        st(int a,int b)
        {
            to=a,cost=b;
        }
    };
    
    int dis[505];
    queue<int> q;
    vector<st> v[505];
    int n,m,w;
    int cnt[505];
    bool vis[505];
    
    void init()
    {
        for(int i=0;i<=n;i++)
        {
            v[i].clear();
        }
        while(!q.empty())
            q.pop();
        mem(dis,inf);
        mem(vis,0);
        mem(cnt,0);// 竟然忘记写了
    }
    
    bool spfa()
    {
        q.push(1);
        vis[1]=1;
        dis[1]=0;
        cnt[1]=1;
        while(!q.empty())
        {
            int now=q.front();
            q.pop();
            vis[now]=0;
            for(int i=0;i<(int)v[now].size();i++)
            {
                st t=v[now][i];
                if(dis[t.to]>dis[now]+t.cost)
                {
    
                    dis[t.to]=dis[now]+t.cost;  //开始写错了
                    if(!vis[t.to])
                    {
                        vis[t.to]=1;
                        q.push(t.to);
                        cnt[t.to]++;
                        if(cnt[t.to]>=n)return 0;
                    }
                }
            }
        }
        return 1;
    }
    
    int main()
    {
    
        int T=in();
        while(T--)
        {
            n=in(),m=in(),w=in();
            init();               ///  开始的时候竟然没写！！！
            for(int i=1;i<=m;i++)
            {
               int t1=in(),t2=in(),cost=in();
               v[t1].push_back(st(t2,cost));
               v[t2].push_back(st(t1,cost));
            }
            for(int i=1;i<=w;i++)
            {
                int t1=in(),t2=in(),cost=in();
                v[t1].push_back(st(t2,-cost));
            }
            if(!spfa())puts("YES");
            else puts("NO");
        }
        return 0;
    }