問題一覧 > 通常問題

No.1805 Approaching Many Typhoon

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 72
作問者 : matcharate12matcharate12 / テスター : Namu3Namu3
0 ProblemId : 6958 / 自分の提出
問題文最終更新日: 2022-04-01 11:33:56

※問題の不備の修正について

1/12 20:58 テストケースに不備が見つかりましたので、修正が終わり次第リジャッジします。申し訳ございませんでした。
また問題文とケースが矛盾しているところがありました。問題文が間違っていたので修正します。
1/12 21:12 リジャッジが完了しました。また問題文を修正しました。申し訳ございませんでした。
1/12 21:45 問題文の制約と矛盾しているケースがありました。リジャッジを行いました。
1/12 22:10 問題文を改正しました。
1/13 15:31 質問があったので、その内容をもとに問題文を改正しました。
1/16 16:58 質問から問題文に不備が見つかりましたので訂正しました。申し訳ありませんでした。

問題文

小さい島、ここyuki島にはmatcharate君が住んでいます。ここの付近の海域では N 島の島と、M 便の船があります。
それぞれ島には 1,2,3,...N の番号が付けられており、i (1iM) 番目の便は島 Fi と島 Ti2 つの島の間で行き来できる船が用意されています。

...ところが今日の夜、U 個の台風が近づいていて、明日になる前に j (1jU) 番目の島 Ij を経由することは危険だと判断し、その島を閉鎖することになってしまいました。
そして夜が更け、出発することになりました。matcharate君は島 Ij を経由せずに島 S から島 G に到着することはできるでしょうか?

入力

N M
S G
F1 T1
F2 T2
:
FM TM
U
I1 I2  IU
2N2000
1SGN
1Mmin(N(N1)2,2000)
1FiTiN
0U500
1IjNIjSIjG

・追記: 1/12 21:12 U の制約を間違えておりました。申し訳ございませんでした。U=0 になりうることにも注意してください。

出力

可能なら

Yes
を、不可能なら
No
と出力してください。

サンプル

サンプル1
入力
3 3
1 2
1 3
3 2
1 2
1
3
出力
Yes

3 は台風が近づいていて危険です。この場合、島 1 から島 2 に到着するための便が存在するのでたどり着くことができます。

サンプル2
入力
5 6
1 5
1 3
1 4
1 2
2 4
2 3
5 4
2
2 4
出力
No

2,4 が閉鎖しています。島 5 からは島 4 の便だけです。この場合は島 4 を経由する必要があるので、たどり着くことはできません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。