T4Solution

崔化博 · 2022-08-29 14:09:42 · 个人记录

为了方便我们规定 0 一开始就被传染，第 i 个人 a_i 分钟出来等于第 i 个人在第 a_i 分钟与 0 接触。

我们可以从 n 点出发，求一条非递增路径，一直到 0 点，我们要求其中最大的边权也就是经过的第一条边最小，当然，可能有环，因此我们设 f_i 表示 i 所经过的最小的最大的路径也就是一开始在第 n 个点经过的边后到达这个点后让这条边最小的值，只要判断 f_i 大于经过的第一条边时才访问第 i 个点，从第 n 个点dfs 开始就可以了。