H - お風呂は気持ちいい
Editorial
/
この世界では魔法使いは、魔導石から魔力をもらって魔法をつかい、M人の魔法使いが存在します。
魔力は人から人へと渡すことができますが、人同士で相性があり、受け渡しの得手不得手もあるので、渡せる量は決まっています。
魔導石からは無制限に魔力が湧き出てくるので、魔導石の近くならばどんな魔法でも使うことができ、いくらでも魔力を得ることができます。
また、魔法使いは魔力を蓄積することはできません。
アスナさんは、お風呂に入りたいのですが、お風呂を沸かすためには魔力が必要です。
あいにく残念なことに、アスナさんの家は魔導石からは離れています。
他の人は気前よく魔力をくれるので、他の人に魔力を経由してもらうことにしましたが、どのぐらい魔力が得られるのかがわかりません。
経由できるルートと、使いたい魔法に必要な魔力が与えられるので、お風呂を沸かせるならば"Yes"そうでないならば"No"と出力してください。
N個のルートと、魔法使いの人数M、お風呂を沸かすのに必要な魔力P、魔導石に近いところにいる魔法使いの人数G、及び、魔導石に近いところにいる魔法使いのリストと、魔法使いの間の魔力の受け渡しのルートのリストが与えられます。
魔法使いはそれぞれ番号が割り振られており、アスナさんの番号は0です。
また、各魔法使いxについて,xが渡せる魔力の総量は,xが受け取った魔力の総量以下です。
入力は以下の形式で与えられます。
入力中は各変数はすべて整数である。また、以下の制約を満たす。
上記の制約に、
from_i - 1 = to_i
を加えたテストケースいくつかに正答すると40点を獲得できる。
アスナさんが受け取れる魔力が、お風呂を沸かすのに必要な魔力以上ならば"Yes"、そうでないならば"No"と一行で出力してください。
Time Limit: 2 sec / Memory Limit: 256 MB
問題文
入力
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)
部分点
出力
入力例 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