| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 | 1024 MB | 73 | 46 | 41 | 64.062% |
There are $n$ dragons numbered from 1ドル$ to $n$. Dragon $i$ has age $a_i$. The values of $a_i$ are distinct. Dragon 1ドル$ is Evirir the dragon.
Evirir has a letter it wants to send to dragon $t$. To avoid awkwardness caused by age difference, Evirir can send the letter to another dragon (not necessarily dragon $t$). The dragon who received the letter can then send the letter to another dragon, and so on. The goal is to eventually send the letter to dragon $t$.
For all $i$ (1ドル \le i \le n$), when dragon $i$ has the letter, it can send the letter to dragon $j$ in $|a_i - a_j|$ time$^1$. A dragon can "send" the letter to itself in 0ドル$ time. However, there are $k$ pairs of dragons who are close friends. If dragons $i$ and $j$ are close friends, then it takes 0ドル$ time instead for dragon $i$ to send a letter to dragon $j$ (and vice versa).
For each dragon $t$ (1ドル \le t \le n$), answer the question (independently): What is the minimum total time needed for dragon 1ドル$ to send a letter to dragon $t$?
$^1$Note: $|x|$ denotes the absolute value of $x$. For example, $|9| = 9,ドル $\lvert -6 \rvert = 6,ドル and $|0| = 0$. See \url{https://en.wikipedia.org/wiki/Absolute\_value} for more information.
The first line contains two space-separated integers $n$ and $k$ (1ドル \le n\le 2 \cdot 10^5,ドル 0ドル \le k \le 2 \cdot 10^5$) -- the number of dragons and the number of pairs of close friends.
The second line contains $n$ distinct space-separated integers $a_1, a_2, \ldots, a_n$ (1ドル \le a_i \le 10^9$) -- the dragons' ages.
Then, $k$ lines follow. Each of the $k$ lines contains two space-separated integers $u$ and $v$ (1ドル \le u, v \le n,ドル $u \ne v$), which means that dragons $u$ and $v$ are close friends. It is guaranteed that the same pair of close friends will not appear twice (if $(u,v)$ appears, then $(u,v)$ and $(v,u)$ will not appear afterwards).
Output $n$ space-separated integers $d_1, d_2, \ldots, d_n,ドル where $d_i$ is the minimum total time needed for dragon 1ドル$ to send the letter to dragon $i$.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 18 | $n, k \le 2000,ドル $a_i = i$ |
| 2 | 14 | $n, k \le 2000$ |
| 3 | 9 | $k = 0$ |
| 4 | 29 | $a_i = i$ for all $i$ (1ドル \le i \le n$) |
| 5 | 16 | The sequence $a$ is non-decreasing, i.e. $a_i \le a_{i+1}$ for 1ドル \le i \le n-1$ |
| 6 | 14 | No additional constraints |
8 4 50 30 23 10 3 67 69 47 3 7 3 1 2 4 7 1
0 7 0 7 14 2 0 3
3 0 2 3 1
0 1 1
Explanation for the first sample:
When $t = 1,ドル it takes 0ドル$ time because dragon 1ドル$ already has the letter.
When $t = 3,ドル since dragon 1ドル$ and 3ドル$ are close friends, dragon 1ドル$ can send the letter directly to dragon 3ドル$ in 0ドル$ time.
When $t = 2,ドル dragon 1ドル$ can send the letter to dragon 3ドル$ first in 0ドル$ time (they are close friends), then dragon 3ドル$ sends the letter to dragon 2ドル$ in $|23 - 30| = 7$ time. The total time taken is 0ドル + 7 = 7$.
When $t = 8,ドル dragon 1ドル$ can just send the letter directly to dragon 8ドル,ドル taking $|50 - 47| = 3$ time.
Here is one optimal way each for the remaining $t$'s ($i \xrightarrow{x} j$ means dragon $i$ sends the letter to dragon $j$ using $x$ time):