問題一覧 > 通常問題

No.3326 Iwai Alien's Return Home

レベル : / AI推定難易度 : 1275 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 56
作問者 : yimiya(いみや) / テスター : DeltaStruct 👑 loop0919 ゆにたりー卿 あじゃじゃ elphe bolero のらら
お気に入りにしたユーザー ProblemId : 12026 / 自分の提出
問題文最終更新日: 2025-10-31 19:39:40
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
第2回 岩井星人アンソロジープログラミングコンテスト Extra (順位表) の他の問題:

Story

Iwai Alien, who is on Earth, has received an interstellar message from his mother living on Planet Iwai: "Come back to Planet Iwai soon."

Since Iwai Alien does not want to worry his mother, he has decided to send a message to Planet Iwai by interstellar communication telling her how many days it will take him to return, and then head home.

However, nowadays many space telescopes are monitoring space, and if the spaceship Iwai Alien is riding in is spotted by a space telescope, it will be tracked, Planet Iwai will be discovered by Earth's researchers, and it will be turned into a testing ground.

Therefore, he must not be spotted by any space telescope on his way back to Planet Iwai.

Problem Statement

You are given a simple undirected graph with $N$ vertices and $M$ edges. The graph consists of vertex $1$, vertex $2$, $\dots$, vertex $N$, and the $i\ (1 \leq i \leq M)$-th edge connects vertex $u_i$ and vertex $v_i$.

Iwai Alien travels from vertex $1$ to vertex $N$ along the edges. For each vertex, moving to an adjacent vertex takes $1$ day.

There are also $L$ space telescopes, and the $i\ (1 \leq i \leq L)$-th space telescope monitors all vertices whose travel time from vertex $J_i$ is at most $K_i$ days.

If Iwai Alien can travel from vertex $1$ to vertex $N$ without passing through any monitored vertex, output Yes and the minimum number of days required to travel from vertex $1$ to vertex $N$; otherwise, output No.

Constraints

  • $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$
  • If $i \ne \ j$, then $(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$

Input

$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$ 

Output

If Iwai Alien can travel to vertex $N$ without passing through any monitored vertex, output Yes, then a newline, then the minimum number of days to vertex $N$; otherwise, output No.


Sample

Sample 1
Input
6 6
1 2
1 3
2 6 
3 4 
4 5 
5 6 
1
4 1 
Output
Yes
2

There are two routes to Planet Iwai: [Earth, Planet 2, Planet Iwai] and [Earth, Planet 3, Planet 4, Planet 5, Planet Iwai]. However, since the space telescope monitors Planet 4 and Planets 3 and 5, which are within distance 1 of Planet 4, he must not take the route [Planet 1, Planet 3, Planet 4, Planet 5, Planet 6].

On the other hand, nothing on [Earth, Planet 2, Planet Iwai] is monitored, so he can return to Planet Iwai.

Therefore, output Yes, then a newline, and then 2.

Sample 2
Input
3 2
1 2
1 3
1
3 1 
Output
No

Planet Iwai itself is monitored, so it is impossible to go there.

Sample 3
Input
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
Output
Yes
6

When the distance from the center is 0, the only planet monitored is the center planet itself.

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