#P3259. Wormholes
Wormholes
题目描述
在探索自己的众多农场时,Farmer John 发现了一些神奇的虫洞。虫洞的特别之处在于它是单向路径,能将你送到比进入时更早的时间点!John 的每个农场包含 ()块田地(编号 1 到 )、()条路径,以及 ()个虫洞。
作为狂热的时间旅行爱好者,John 想尝试:从某块田地出发,经过若干路径和虫洞后,回到起点时的时间早于出发时间(或许能遇到过去的自己)。为了帮助 John 确定是否可行,他提供了 ()个农场的完整地图。所有路径的通行时间不超过 10,000 秒,虫洞的时间回溯不超过 10,000 秒。
输入格式
- 第 1 行:整数 ,表示农场数量。
- 每个农场的输入:
- 第 1 行:三个整数 。
- 第 2 到 行:每行三个整数 ,表示 和 之间的双向路径,通行需 秒(可能存在多条路径)。
- 第 到 行:每行三个整数 ,表示从 到 的单向虫洞,时间回溯 秒。
输出格式
- 对每个农场,输出 "YES"(存在时间回路)或 "NO"(不存在)。
输入样例 1
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
输出样例 1
NO
YES
样例解释
- 农场 1:无法找到时间回路。
- 农场 2:路径 1→2→3→1 构成时间回路,回到起点时比出发早 1 秒。
来源
USACO 2006 十二月金牌赛