danihao123's Blog

呜……这题现在才A

这道题就是给一个图让判断有没有负环，没什么难度

然后……我写邻接表竟然开小内存了……

尽管如此我感觉我写此题时的代码风格还是不错的，比较值得学习

代码：

/**************************************************************
    Problem: 1715
    User: danihao123
    Language: C++
    Result: Accepted
    Time:92 ms
    Memory:920 kb
****************************************************************/
 
#include <cstdio>
#include <queue>
#include <cstring>
#include <cctype>
using namespace std;
const int maxn=501,maxm=5201;
namespace Graph{
    int n;
    int first[maxn];
    int next[maxm],to[maxm],dist[maxm];
    int tot=0;
    inline void AddEdge(int u,int v,int d){
        tot++;
        next[tot]=first[u];
        first[u]=tot;
        to[tot]=v;
        dist[tot]=d;
    }
    inline void ClearGraph(){
        memset(first,0,sizeof(first));
        memset(next,0,sizeof(next));
        memset(to,0,sizeof(to));
        memset(dist,0,sizeof(dist));
        tot=0;
    }
    int cnt[maxn];
    bool inQueue[maxn];
    int d[maxn];
    bool SPFA(){
        register int i,u;
        queue<int> Q;
        memset(cnt,0,sizeof(cnt));
        memset(inQueue,0,sizeof(inQueue));
        for(i=1;i<=n;i++){
            d[i]=0;
            cnt[i]=1;
            inQueue[i]=true;
            Q.push(i);
        }
          
        while(!Q.empty()){
            u=Q.front();
            Q.pop();
            inQueue[u]=false;
            for(i=first[u];i;i=next[i]){
                if(d[to[i]]>d[u]+dist[i]){
                    d[to[i]]=d[u]+dist[i];
                    if(!inQueue[to[i]]){
                        Q.push(to[i]);
                        inQueue[to[i]]=true;
                        if(++cnt[to[i]]>n)
                            return true;
                    }
                }
            }
        }
        return false;
    }
};
inline int readint(){
    register char c;
    register int temp=0;
    c=getchar();
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        temp=temp*10+c-'0';
        c=getchar();
    }
    return temp;
}
int main(){
    register int i,m,w,u,v,d;
    int F;
    F=readint();
    while(F--){
        Graph::n=readint();
        m=readint();
        w=readint();
        Graph::ClearGraph();
        for(i=1;i<=m;i++){
            u=readint();
            v=readint();
            d=readint();
            Graph::AddEdge(u,v,d);
            Graph::AddEdge(v,u,d);
        }
        for(i=1;i<=w;i++){
            u=readint();
            v=readint();
            d=readint();
            Graph::AddEdge(u,v,-d);
        }
        if(Graph::SPFA())
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}