虫洞(Wormholes)

题目描述

Farmer John 在探索他的农场时发现了许多神奇的虫洞。虫洞的特性非常特殊——它是一个单向通道，能将你传送到它的目的地，而且时间还会回溯到过去！FJ 的每个农场包含 $N (1 \le N \le 500)$ 块编号为 $1 \sim N$ 的田地、$M (1 \le M \le 2500)$ 条双向路径和 $W (1 \le W \le 200)$ 个虫洞。

作为狂热的时间旅行爱好者，FJ 希望实现：从某块田地出发，经过若干路径和虫洞后，在初始离开时间之前回到起点。这样或许他能遇见自己 :)

为了判断可行性，FJ 将提供 $F (1 \le F \le 5)$ 个农场的完整地图。所有路径通行耗时不超过 $10,000$ 秒，虫洞最多能将 FJ 带回 $10,000$ 秒前。

输入格式

第 $1$ 行：一个整数 $F$，表示农场数。后续为 $F$ 个农场的数据。

每个农场：

• 第 $1$ 行：三个空格分隔的整数 $N$（田地数）, $M$（双向路径数）, $W$（虫洞数）。

• 第 $2 \sim M+1$ 行：每行三个空格分隔的整数 $(S, E, T)$，表示 $S$ 和 $E$ 间有一条耗时 $T$ 秒的双向路径。两块田地间可能存在多条路径。

• 第 $M+2 \sim M+W+1$ 行：每行三个空格分隔的整数 $(S, E, T)$，表示一条从 $S$ 到 $E$ 的单向虫洞，可将 FJ 带回 $T$ 秒前。

输出格式

输出 $F$ 行：对每个农场，若 FJ 能达成目标输出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$：FJ 无法实现时间回溯。

• 农场 $2$：FJ 可通过环 $1 \to 2 \to 3 \to 1$ 回到起点 $1$ 秒前（可从环上任意点出发实现）。

对于 $100\%$ 的数据，$1 \le F \le 5$，$1 \le N \le 500$，$1 \le M \le 2500$，$1 \le W \le 200$，$1 \le T \le 10^4$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1550。

测试点分布

出处：原题链接