p7997题解

· · 题解

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

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

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

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

然后直接在线回答即可