TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1146
  • 题目
  • P1146虫洞
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    农民约翰在巡查他的农场的时候发现了一些惊人的“虫洞”(“虫洞”的详情请参阅按因斯坦的解释)。虫洞非常奇特,它是一个单向通道,可以在瞬间把你传送到通道的另外一端,到达以后你会发现当前时间比你进洞时间要早(简单地说就是穿越了,回到了过去)。约翰的农场共有N块田,编号1到N,田与田之间共有M条小路相连(两块田间可能有多条小路相连)。约翰在这些田上总共找到了W个虫洞。
    约翰是个穿越爱好者,他想做下面这些事:以某块田为起点出发,穿过一些小路和虫洞,然后回到起点,使他回到起点时的时间早于他出发的时间,也许这样他就能在起点上见到另一个他自己了。
    为了帮助约翰知道他的方案能否可行,他会给你整个农场的地图。走过一条小路的耗时不会超过10000秒。一个虫洞一次最多能使时间倒退10000秒。

    输入格式

    第一行一个整数F,表示有F组测试数据。
    对于每组测试数据:
    第1行有三个整数N,M和W
    接下来M行,每行三个空格间隔的整数S,E,T分别表示一条小路的起点,终点和通过所需时间。
    接下来W行,每行三个空格间隔的整数S,E,T分别表示一个虫洞穿越的起点,终点和让时间倒退的秒数。

    输出格式

    包括F行,每行一个单词。"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

    样例输入 2

    5
    5 10 2
    1 3 277
    3 5 7116
    5 5 3567
    2 4 6023
    5 3 1453
    3 1 1083
    4 1 2414
    1 3 8174
    2 5 6055
    3 2 9029
    3 5 1466
    2 5 88
    5 10 2
    2 4 8688
    3 2 619
    3 5 9103
    5 5 6657
    5 3 8188
    3 3 7513
    5 1 9068
    1 3 5184
    4 5 8318
    4 3 3706
    5 3 591
    5 2 1605
    5 10 2
    4 3 7819
    3 1 4797
    4 3 6176
    1 3 6207
    2 1 9643
    3 1 2436
    2 5 2302
    3 5 401
    4 2 3435
    2 2 4987
    5 3 1173
    3 4 1078
    5 10 2
    1 5 9720
    5 2 7917
    1 5 5038
    2 4 6890
    3 5 9688
    1 5 1063
    1 3 5468
    5 2 5244
    2 2 435
    1 5 5763
    5 4 293
    1 2 929
    5 10 2
    4 3 66
    4 4 8651
    3 4 8304
    4 5 7845
    2 3 2923
    1 3 5425
    1 1 526
    5 4 2853
    1 3 4244
    5 3 6174
    2 5 1090
    1 4 103

    样例输出 2

    YES
    NO
    YES
    NO
    NO

    提示

    【数据范围】
    1<=N<=500
    1<=M<=2500
    1<=W<=200
    1<=F<=5