自动搬运

查看原文

来自洛谷，原作者为

	€€£ 中国收钱协会(€hina€ounting£oundation)唯一官方认证账号，有事欢迎@（有时候可能不在）||https://www.luogu.com.cn/paste/hm8t61yq

搬运于2025-08-24 22:35:02，当前版本为作者最后更新于2021-12-28 18:31:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

容易发现，最大的答案 $<2 \times a_{max}$​

容易发现，一个点若能够在 $x$ 时刻到达，则一定能在 $x+2$ 时刻到达

于是我们将一个点拆点，拆成奇数步到达以及偶数步到达

之后我们再连边并预处理出最短路

然后直接在线回答即可