#P3259. Wormholes

    ID: 2260 传统题 2000ms 256MiB 尝试: 2 已通过: 1 难度: 10 上传者: 标签>USACO 2006 December Gold图论最短路径负权环检测贝尔曼-福特算法

Wormholes

题目描述

在探索自己的众多农场时,Farmer John 发现了一些神奇的虫洞。虫洞的特别之处在于它是单向路径,能将你送到比进入时更早的时间点!John 的每个农场包含 NN1N5001 \leq N \leq 500)块田地(编号 1 到 NN)、MM1M25001 \leq M \leq 2500)条路径,以及 WW1W2001 \leq W \leq 200)个虫洞。

作为狂热的时间旅行爱好者,John 想尝试:从某块田地出发,经过若干路径和虫洞后,回到起点时的时间早于出发时间(或许能遇到过去的自己)。为了帮助 John 确定是否可行,他提供了 FF1F51 \leq F \leq 5)个农场的完整地图。所有路径的通行时间不超过 10,000 秒,虫洞的时间回溯不超过 10,000 秒。

输入格式

  • 第 1 行:整数 FF,表示农场数量。
  • 每个农场的输入:
    • 第 1 行:三个整数 N,M,WN, M, W
    • 第 2 到 M+1M+1 行:每行三个整数 (S,E,T)(S, E, T),表示 SSEE 之间的双向路径,通行需 TT 秒(可能存在多条路径)。
    • M+2M+2M+W+1M+W+1 行:每行三个整数 (S,E,T)(S, E, T),表示从 SSEE 的单向虫洞,时间回溯 TT 秒。

输出格式

  • 对每个农场,输出 "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 十二月金牌赛