题目描述
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N（从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。
输入格式
Line 1: 一个整数 F, 表示农场个数。
Line 1 of each farm: 三个整数 N, M, W。
Lines 2..M+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地，中间有一条用时T秒的小路。
Lines M+2..M+W+1 of each farm: 三个数（S, E, T）。表示在标号为S的地与标号为E的地，中间有一条可以使John到达T秒前的虫洞。
输出格式
Lines 1..F: 如果John能在这个农场实现他的目标，输出"YES",否则输出"NO"
由于题中所说，M条无向边已经连接了N个点，所以所有虫洞都必定属于至少一个简单环。
所以这题只需要判一下负环即可，这里我们可以用到SPFA。我们不停地将节点松弛，直到某个节点被松弛了超过n次，就说明有负环。
这种方法比较低效，这里介绍一种更高效的。记cnt[u]表示u到起点经过多少个点。那么每次松弛：if(dis[v]>dis[u]+edge(u,v)) then dis[v]=dis[u]+edge(u,v)时，我们令cnt[v]=cnt[u]+1。显然，起点到终点的最短路不会超过n-1个节点(起点不算)。那么我们松弛时一旦发现cnt[v]=n-1就说明有负环。
时间复杂度都是O(KM)，但第二种明显更高效：第一种要将v入队n次才能判负环，而第二种只需要((n-1)/环的节点数)次即可。
#include #include #include #include #define maxn 100001#define maxm 100001#define maxw 201using namespace std; struct edge{ int to,dis,next; edge(){} edge(const int &_to,const int &_dis,const int &_next){ to=_to,dis=_dis,next=_next; }}e[maxm*2+maxw];int head[maxn],k; int dis[maxn],cnt[maxn];bool inq[maxn];int n,m,w; inline int read(){ register int x(0),f(1); register char c(getchar()); while(c<'0'||'9'
q; q.push(1),inq[1]=true,dis[1]=0; while(q.size()){ int u=q.front(); q.pop(),inq[u]=false; for(register int i=head[u];~i;i=e[i].next){ int v=e[i].to; if(dis[v]>dis[u]+e[i].dis){ dis[v]=dis[u]+e[i].dis,cnt[v]=cnt[u]+1; if(cnt[v]>=n) return true; if(!inq[v]) q.push(v),inq[v]=true; } } } return false;} int main(){ int t=read(); while(t--){ memset(head,-1,sizeof head); n=read(),m=read(),w=read(); for(register int i=1;i<=m;i++){ int u=read(),v=read(),w=read(); add(u,v,w),add(v,u,w); } for(register int i=1;i<=w;i++){ int u=read(),v=read(),w=read(); add(u,v,-w); } printf("%s\n",spfa()?"YES":"NO"); } return 0;}