P9720 [EC Final 2022] Map

有一个著名的数学定理，如果你把一张公园的地图完全放在公园里，那么地图上存在一个点与它所代表的点重合。 Mio 非常喜欢这个定理，所以她把她最喜欢的公园的地图完全放在了公园里。公园 $P$ 可以用一个矩形表示。公园的地图只是一个较小（或相等）版本的公园在纸上的打印。地图与原始矩形相似。地图上的每个点都通过相似变换对应于公园中的一个点。 我们可以正式定义地图：地图是一个矩形 $M$（大小较小或相等），加上一个正实数 $r$ 和一个双射函数 $f:M \rightarrow P$，满足以下条件： - 对于 $M$ 中的每对不同的点 $a, b$，$|f(a)-f(b)|/|a-b|=r$。 这里 $|x-y|$ 表示点 $x$ 和点 $y$ 之间的欧几里德距离。 就像许多游戏一样，Mio 可以使用地图进行传送。准确地说，当 Mio 在地图上的某个点 $x$（包括边界）时，她可以传送到公园中相应的点 $f(x)$。她也可以选择不传送。反之亦然。当她在公园中的点 $y$（包括边界）时，她可以传送到代表她当前位置的地图上的点 $f^{-1}(y)$。她也可以选择不传送。 Mio 最多可以传送 $n$ 次（最少为 $0$ 次）。每次传送需要 $k$ 秒。Mio 还可以以每秒 $1$ 个单位的速度步行。 给定两个点 $s$ 和 $t$，找出 Mio 从 $s$ 到 $t$ 需要的最短时间。 每次传送可以是任意方向（从地图到公园，或从公园到地图）。地图可以倒置放置。由于地图位于公园内部，所以 Mio 可能同时在地图上和在公园中。在这种情况下，她可以选择传送的方向。 例如，在下图中，公园是 $ABCD$，地图是 $A'B'C'D'$。当 Mio 在地图上时，她同时在地图上和在公园中。当她在点 $D'$ 时，她可以从地图传送到公园（到达 $D$），并从公园传送到地图（到达 $D^{\prime\prime}$）。 

无

无