1715

这个 $k$ 非常小，所以我们考虑全部依次飞这 $k$ 次行程。 这个飞来飞去是一个平方的形式，我们考虑优化这一形式。 首先我们知道从 $u$ 飞到 $v$ 后就可以这样做： $$dis_u + (u -v)^2 \to dis_v$$ $$dis_u + u^2 + v^2 - 2uv \to d ......