题解

思路推导

先从顶点 $1$ 做 BFS 得到最短距离 $d$。沿一条满足 $d_u<d_v$ 的边前进时距离严格增大，因此这些边构成按距离分层的有向无环关系。

设 $f_u$ 为从 $u$ 出发按规则能够到达的最小距离。若边 $u\to v$ 满足 $d_v\le d_u$，经过它就使用了唯一一次非上升机会，之后能得到的最小值至少包含 $d_v$；若 $d_v>d_u$，还没有使用这次机会，可以继续采用 $f_v$。

做法

按 $d$ 从大到小处理顶点，初始令 $f_u=d_u$。枚举 $u$ 的每条出边：当 $d_v>d_u$ 时用 $f_v$ 更新；否则用 $d_v$ 更新。因为第一类边总指向更大的距离，处理 $u$ 时所需的 $f_v$ 已经计算完成。

正确性证明

从 $u$ 出发的合法路径要么停在 $u$，要么第一步走向某个 $v$。若 $d_v\le d_u$，这一步已经使用唯一一次非上升边，之后只能沿距离严格增加的边，因此路径上最小距离就是不大于 $d_v$ 的候选，转移取 $d_v$ 足以覆盖最优值。若 $d_v>d_u$，规则状态没有改变，后续最优值正是 $f_v$。算法枚举全部第一步并与停留方案取最小，所以得到准确的 $f_u$。

严格上升边只指向更大距离，逆距离顺序满足所有依赖，故归纳可知每个状态都正确。

复杂度分析

每个测试用例的时间复杂度为 $O(n+m)$，空间复杂度为 $O(n+m)$。