P9289 [ROI 2018] Quantum teleportation

Translated from [ROI 2018 Day1](https://neerc.ifmo.ru/school/archive/2017-2018.html) T4. [Квантовая телепортация ](https://neerc.ifmo.ru/school/archive/2017-2018/ru-olymp-roi-2018-day1.pdf) ([Quantum teleportation](https://codeforces.com/gym/102147/problem/C))。

On a 2D Cartesian coordinate plane, there are $k$ CPUs numbered $1 \dots k$. The position of each CPU can be represented by coordinates on the plane. CPU $1$ is located at $(1,1)$, and CPU $k$ is located at $(n,m)$. It is guaranteed that all CPUs are on integer grid points, and for each CPU with coordinates $(x_i, y_i)$, it holds that $1 \le x_i \le n$ and $1 \le y_i \le m$. The time for CPU $i$ to transmit a piece of data to CPU $j$ via the bus is ${2^{\max(|x_{{i}}-x_{{j}}|,|y_{{i}}-y_{{j}}|)}}$ time units. Find the minimum time needed to send the data from CPU $1$ to CPU $k$, and output one valid plan.

The first line contains three integers $n,m,k$. The next $k$ lines each contain two integers $x_i,y_i$.

The first line contains an integer $L$, which denotes how many CPUs are visited in the fastest plan. The second line contains $L$ integers, denoting the CPUs visited in order. If there are multiple paths with the minimum time, output any one of them.

For all testdata, $2 \leq n,m,k \leq 10000$. ## Constraints | Subtask ID | $n,m,k$ | Special Property | | :----------: | :----------: | :----------: | | $1$ | $2 \leq n,m,k \leq 20$ | None | | $2$ | $2 \leq n,m,k \leq 500$ | None | | $3$ | $2 \leq n,m,k \leq 10000$ | There is only one CPU in each row and each column | | $4$ | $2 \leq n,m,k \leq 10000$ | None | Translated by ChatGPT 5