← 返回题目列表

AtCoder · qupc2014_h

H. 洗澡的感觉真好

中文机器翻译题面 查看原题

問題文

在这个世界上,有M位魔法师,他们通过从魔法石中获得魔力来使用魔法。 魔力可以在人与人之间传递,但可以传递的数量是固定的,因为每个人彼此兼容,并且在传递魔力方面都有长处和短处。 魔力从魔石中涌出,没有限制,所以只要靠近魔石,就可以使用任何你想要的魔法,想要多少魔力就可以获得多少。 而且,巫师无法积累魔力。 亚丝娜想要洗澡,但她需要魔力来加热浴缸。 不幸的是,亚丝娜的家距离魔石很远。 其他人慷慨地给我魔力,所以我决定让别人给我他们的魔力,但我不知道我能得到多少魔力。 你会得到你可以走的路线以及你想要使用的魔法所需的魔力,所以如果你想烧水,就输出“是”,否则输出“否”。

入力

给你N条路线,巫师人数M,煮个澡所需的魔力P,魔法石附近巫师的数量G,魔法石附近巫师的列表,以及魔法师之间转移魔力的路线列表。 每个巫师都有一个编号,而亚丝娜的编号是0。 并且,对于每个巫师x,x能够转移的魔力总量小于或等于x已经接收的魔力总量。 输入按以下格式给出:
N M P G
L_0 ・・・ L_{G-1}
from_0 to_0 cap_0
・
・
・
・
from_{N-1} to_{N-1} cap_{N-1}
L_0 … L_{G-1}是魔法石附近魔法师的编号。 from_i、to_i、 cap_i分别是, 编号为from_i的魔术师to_i可以交给负责的魔法师的最大魔力是cap_i。

制約

输入时,所有变量均为整数。此外,还满足以下约束条件。 当
  • 1≦N≦500
  • 1≦M≦100
  • 0≦G≦10
  • 0≦P≦1000
  • 0≦from_i,to_i<M
  • 1≦cap_i≦1000
  • i≠j当时L_i ≠ L_j。 还有全部 关于i关于L_i≠0。
  • 全部i, 当我输入from_i≠to_i。
  • 任何0≦i<j<N, 您可以获得(from_i,to_i)≠(from_j,to_j)

部分点

由于上述限制, 通过正确回答一些测试用例(包括 from_i - 1 = to_i ),您可以获得 40 分。

出力

如果亚丝娜能够接收到的魔力大于煮澡所需的魔力,则输出“Yes”,否则输出“No”一行。

入力例 1

1 2 100 1
1
1 0 200

出力例 1

Yes

入力例 2

1 3 100 1
1
2 1 200

出力例 2

No

入力例 3

4 5 100 2
3 4
1 0 200
2 1 50
3 2 100
4 2 100

出力例 3

No