1. P9126 [USACO23FEB] Moo Route II S
首先注意到不一定保证 \(r_i\le s_i\)，否则就是最短路裸题了。
注意到此时相当于负权图最短路。spfa 也许能过，但是我们想要复杂度确定的写法。
利用一下一条边出入时间固定（至少中途不会变）的性质：不难发现每条边最多只会走一次。不妨考虑 dfs，记录当前的位置和时间。考虑扩展，记当前的时间为 \(t\)，则一条变能走需要满足 \(r\ge t\)。不难对每个点出边按 \(r\) 降序排序之后满足条件的是一段前缀。使用 vector 存图，每次记录一下当前弧，搜索即可。
注意当前弧要在 dfs 下去之后更新，不然如果出现环就寄了。可以参考代码。
时间复杂度 \(O(n\log n)\)，瓶颈在排序。
标签：考前,短路,SDOI2024,dfs,当前,复杂度 From： https://www.cnblogs.com/syzqwq/p/18037188