No.3326 Iwai Alien's Return Home
タグ : / 解いたユーザー数 56
作問者 :
yimiya(いみや)
/ テスター :
DeltaStruct
👑
ゆにたりー卿
あじゃじゃ
bolero
のらら
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もしくは右上の雲マークをクリックしてアカウントを作成してください。