【JOI 2017 Final】足球 / Soccer

P5100 [JOI 2017 Final] 足球 / Soccer - 洛谷

在二维网格球场上有 $N$ 名球员，求通过球员移动/运球（每步疲劳度为 $C$）以及踢球（踢出距离 $p$ 疲劳度为 $A \times p + B$）相互配合，将足球从 $1$ 号球员处转移到 $N$ 号球员初始位置所需的最小总疲劳度。

$1 \le W, H \le 505, 1 \le A, B, C \le 10 ^ 9, 1\le n \le 10 ^ 5$。

我们考虑到球的状态，球要么是被人带着，要么是在被踢的状态。

考虑拆点做分层图或者拆状态。

我采用的方式是拆状态。

我们设 $d_{x, y, st}$ 表示在 $(x, y)$ 这个位置，状态是 $st$ 的最小花费。

这里我们设 $5$ 种状态，由于被踢的状态是特殊的，我们单独处理。因为被踢的时候只能沿着本方向一直走。我们定义 $\{ 0, 1, 2, 3, 4\}$ 分别表示被踢的时候，上下左右，和被带的时候，分别在最短路的时候转移。

但是被踢转换到被带的时候，需要找到最近的球员进行接球，这个过程需要预处理每一个格子最近的球员，可以用多源的 BFS 完成这个预处理。

时间复杂度 $\mathcal{O}(HW \log (HW))$。