AT_qupc2014_h お風呂は気持ちいい

[problemUrl]: https://atcoder.jp/contests/qupc2014/tasks/qupc2014_h この世界では魔法使いは、魔導石から魔力をもらって魔法をつかい、M人の魔法使いが存在します。 魔力は人から人へと渡すことができますが、人同士で相性があり、受け渡しの得手不得手もあるので、渡せる量は決まっています。 魔導石からは無制限に魔力が湧き出てくるので、魔導石の近くならばどんな魔法でも使うことができ、いくらでも魔力を得ることができます。 また、魔法使いは魔力を蓄積することはできません。 アスナさんは、お風呂に入りたいのですが、お風呂を沸かすためには魔力が必要です。 あいにく残念なことに、アスナさんの家は魔導石からは離れています。 他の人は気前よく魔力をくれるので、他の人に魔力を経由してもらうことにしましたが、どのぐらい魔力が得られるのかがわかりません。 経由できるルートと、使いたい魔法に必要な魔力が与えられるので、お風呂を沸かせるならば"Yes"そうでないならば"No"と出力してください。 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 2 100 1
1
1 0 200
```

 ```
Yes
```


```
1 3 100 1
1
2 1 200
```

 ```
No
```


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

 ```
No
```
                            

N/A

N/A