P9289 ROI 2018 Quantum teleportation 题解

来个复杂度完全不对，但是可以通过的做法！

已知可以分八个方向，每个方向只保留距离最近的点（可能有多个，证明具体看其它题解）。我们暴力建边跑最短路。边的数量经过实践检验不超过 \frac{n^2}4 量级，但其实要建双向边，边数达到了 \frac{n^2}2。

我们不慌！直接跑 Dijkstra！

还要解决存高精度的问题。我们直接用 unsigned long long 压位来模拟。开 160 个 unsigned long long 即可模拟一个高精度数。

代码。用 priority_queue 套结构体直接 MLE 了！

但是我们还是不慌！建一棵线段树，每次可以求出最小值的位置，用线段树代替堆即可。

记 a=160，即表示高精度数所需的变量数量。理论最差时间复杂度 O(n^2a\log n)，空间复杂度 O(n^2+na)。

代码。可能是洛谷只用了部分数据（极限点洛谷需要 5.17s） / LOJ 评测机太快了，所以可以通过。