No.3326 岩井星人の帰星
タグ : / 解いたユーザー数 49
作問者 :
yimiya（いみや）
/ テスター :
DeltaStruct
👑 
loop0919
高橋ゆに
あじゃじゃ
elphe
bolero
のらら
ストーリー
地球にいる岩井星人さんのもとに、岩井星に住んでいるお母さんから「早く岩井星へ帰ってきなさい」という星間通信が送られてきました。
岩井星人さんは母親を心配させたくないため、何日で帰れるかを星間通信で岩井星に送ってから帰ることにしました。
ただし、現代ではたくさんの宇宙望遠鏡が宇宙を監視しており、岩井星人さんの乗っている宇宙船が宇宙望遠鏡に見つかってしまうと、追跡され、岩井星が地球の研究者に見つかって実験場にされてしまいます。
そのため、岩井星へ帰るときに宇宙望遠鏡に見つかってはいけません。
問題文
$N$ 頂点 $M$ 辺の単純無向グラフが与えられます。グラフは頂点 $1$, 頂点 $2$, $\dots$, 頂点 $N$ からなり、 $i\ (1 \leq i \leq M)$ 番目の辺は 頂点 $u_i$ と頂点 $v_i$ を結んでいます。
岩井星人さんは頂点 $1$ から頂点 $N$ まで辺を通って移動します。各頂点について、隣り合う頂点への移動には $1$ 日かかります。
また、 $L$ 個の宇宙望遠鏡が存在し、 $i\ (1 \leq i \leq L)$ 番目の宇宙望遠鏡は頂点 $J_i$ からの移動にかかる日数が $K_i$ 以下である頂点を全て監視しています。
岩井星人さんが監視されている頂点を通ることなく頂点 $1$ から頂点 $N$ まで移動可能ならばYesおよび頂点 $1$ から頂点 $N$ まで移動するのにかかる最短日数を、不可能ならばNoを出力してください。
制約
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq M \leq \min(2 \times 10^5, N(N - 1) / 2)$
- $1 \leq u_i , v_i\leq \ N$
- $u_i \ne\ v_i$
- $i \ne \ j$ ならば $(u_i,v_i) \ne (u_j,v_j)$
- $1 \leq L \leq N$
- $1 \leq J_i \leq N$
- $0 \leq K_i \leq 1000$
入力
$N\ M$ $u_1$ $v_1$ $u_2$ $v_2$ . . $u_M$ $v_M$ $L$ $J_1$ $K_1$ $J_2$ $K_2$ . . $J_L$ $K_L$
出力
岩井星人が監視されている頂点を通ることなく頂点$N$まで移動可能ならYesと出力し改行をした後、頂点$N$との最短日数を、不可能ならNoを出力してください。
サンプル
サンプル1
入力
6 6 1 2 1 3 2 6 3 4 4 5 5 6 1 4 1
出力
Yes 2
岩井星へと経由の仕方は[地球,星2,岩井星]と[地球,星3,星4,星5,岩井星]とありますが、宇宙望遠鏡により星4と星4に近さが1以内である星3,星5が監視されているため[星1,星3,星4,星5,星6]経由してはいけません。
しかし、[地球,星2,岩井星]はどこも監視されてないため岩井星に帰ることができます。
よってYesと出力した後、改行して2を出力します。
サンプル2
入力
3 2 1 2 1 3 1 3 1
出力
No
岩井星そのものが監視されているため行くことは不可能です。
サンプル3
入力
10 11 1 2 2 3 3 4 4 8 4 5 5 6 6 7 6 8 7 8 8 9 9 10 2 7 0 6 0
出力
Yes 6
中心からの距離が0の場合、監視している星は中心となる星だけとなります。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。