[BZOJ 1715]虫洞
呜……这题现在才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; }