Description
John在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John的每个农场有M条小路（无向边)连接着N （从1..N标号）块地，并有W个虫洞。其中1<=N<=500,1<=M<=2500,1<=W<=200。 现在John想借助这些虫洞来回到过去（出发时刻之前），请你告诉他能办到吗。 John将向你提供F(1<=F<=5)个农场的地图。没有小路会耗费你超过10000秒的时间，当然也没有虫洞回帮你回到超过10000秒以前。
Input
* 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秒前的虫洞。
Output
* Lines 1..F: 如果John能在这个农场实现他的目标，输出"YES",否则输出"NO"。
Sample Input
2 3 3 1 1 2 2 1 3 4 2 3 1 3 1 3 3 2 1 1 2 3 2 3 4 3 1 8
Sample Output
NO YES
这道题是SPFA求负环，但是用到的是DFS而不是BFS。每当搜索到一个点已经搜索过，切当前点的dis+路径长比目标点的dis小，那么这个图就存在负环。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <queue>
#define REP(i,k,n) for(int i=k;i<=n;i++)
#define in(a) a=read()
using namespace std;
inline int read(){
int x=
0,f=
1;
char ch=
getchar();
for(;!isdigit(ch);ch=
getchar())
if(ch==
'-')
f=-
1;
for(;isdigit(ch);ch=
getchar())
x=x*
10+ch-
'0';
return x*
f;
}
int T;
int flag=
0;
int n,m,w;
int total=
0,nxt[
6010],head[
550],to[
6510],val[
6510];
int vis[
550],dis[
550];
inline void adl(
int a,
int b,
int c){
total++
;
to[total]=
b;
val[total]=
c;
nxt[total]=
head[a];
head[a]=
total;
return ;
}
inline void dfs(
int u){
for(
int e=head[u];e;e=
nxt[e]){
if(dis[to[e]]>dis[u]+
val[e]){
dis[to[e]]=dis[u]+
val[e];
if(!
vis[to[e]]){
vis[to[e]]=
1;
dfs(to[e]);
vis[to[e]]=
0;
}
else{
flag=
1;
return ;
}
}
}
return ;
}
int main()
{
in(T);
while(T--
){
total=flag=
0;
memset(head,0,
sizeof(head));
memset(to,0,
sizeof(to));
memset(val,0,
sizeof(val));
memset(nxt,0,
sizeof(nxt));
memset(vis,0,
sizeof(vis));
memset(dis,127,
sizeof(dis));
in(n);
in(m);
in(w);
int a,b,c;
REP(i,1,m){
in(a);
in(b);
in(c);
adl(a,b,c);
adl(b,a,c);
}
REP(i,1,w){
in(a);
in(b);
in(c);
adl(a,b,-
c);
}
dis[1]=
0;
vis[1]=
1;
dfs(1);
if(flag) cout<<
"YES"<<
endl;
else cout<<
"NO"<<
endl;
}
}
转载于:https://www.cnblogs.com/jason2003/p/9663700.html
相关资源：JAVA上百实例源码以及开源项目
