1507：虫洞 Wormholes

题目描述

原题来自：USACO 2006 Dec. Gold

John 在他的农场中闲逛时发现了许多虫洞。虫洞可以看作一条十分奇特的有向边，并可以使你返回到过去的一个时刻（相对你进入虫洞之前）。John 的每个农场有 $M$ 条小路（无向边）连接着 $N$（从 $1$ 到 $N$ 标号）块地，并有 $W$ 个虫洞。

现在 John 想借助这些虫洞来回到过去（在出发时刻之前回到出发点），请你告诉他能办到吗。John 将向你提供 $F$ 个农场的地图。没有小路会耗费你超过 $10^4$ 秒的时间，当然也没有虫洞回帮你回到超过 $10^4$ 秒以前。

输入格式

第一行一个整数 $F$，表示农场个数；

对于每个农场：

第一行，三个整数 $N, M, W$；

接下来 $M$ 行，每行三个整数 $S, E, T$，表示在标号为 $S$ 的地与标号为 $E$ 的地中间有一条用时 $T$ 秒的小路（双向）；

接下来 $W$ 行，每行三个整数 $S, E, T$，表示在标号为 $S$ 的地与标号为 $E$ 的地中间有一条可以使 John 到达 $T$ 秒前的虫洞（单向）。

输出格式

输出共 $F$ 行，如果 John 能在第 $i$ 个农场实现他的目标，就在第 $i$ 行输出 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

• 第一个农场：

  • $N=3, M=3, W=1$
  • 小路（双向）：
    1. $1 \leftrightarrow 2$，耗时 $2$ 秒
    2. $1 \leftrightarrow 3$，耗时 $4$ 秒
    3. $2 \leftrightarrow 3$，耗时 $1$ 秒
  • 虫洞（单向）：
    1. $3 \rightarrow 1$，回到 $3$ 秒前（即时间减少 $3$ 秒）
  • 判断是否能回到过去（出发时刻之前回到出发点）：
    • 从 $1$ 出发，走 $1 \rightarrow 2 \rightarrow 3$ 耗时 $2+1=3$ 秒，然后通过虫洞 $3 \rightarrow 1$ 回到 $3$ 秒前，总时间变化 $3-3=0$，回到出发时刻但并非之前，不满足“之前”。
    • 尝试其他路径：$1 \rightarrow 3$ 耗时 $4$ 秒，然后虫洞 $3 \rightarrow 1$ 回到 $3$ 秒前，总时间 $4-3=1$ 秒，仍然在出发之后。
    • 无法找到一条路径使得回到 $1$ 号地时总时间 $<0$，所以输出 NO。

• 第二个农场：

  • $N=3, M=2, W=1$
  • 小路（双向）：
    1. $1 \leftrightarrow 2$，耗时 $3$ 秒
    2. $2 \leftrightarrow 3$，耗时 $4$ 秒
  • 虫洞（单向）：
    1. $3 \rightarrow 1$，回到 $8$ 秒前
  • 判断：从 $1$ 出发，走 $1 \rightarrow 2 \rightarrow 3$ 耗时 $3+4=7$ 秒，然后通过虫洞 $3 \rightarrow 1$ 回到 $8$ 秒前，总时间变化 $7-8 = -1 < 0$，成功在出发时刻之前回到出发点，输出 YES。

数据范围

• $1 \le F \le 5$
• $1 \le N \le 500$
• $1 \le M \le 2500$
• $1 \le W \le 200$
• $1 \le S, E \le N$
• $|T| \le 10^4$

时空限制

• 时间限制：1000 ms
• 内存限制：65536 KB

注意：本题实质是判断图中是否存在负权回路（因为回到过去意味着总时间为负）。可以将虫洞的边权设为 $-T$（因为回到 $T$ 秒前相当于时间减少 $T$），普通小路边权为 $+T$（耗时），然后判断整个图（有向图，因为虫洞是单向，小路是双向需拆成两条有向边）是否存在负环。可以使用 SPFA 或 Bellman-Ford 算法。由于 $N \le 500$，$M+2W \le 2500+400=2900$，算法可行。