首先可以钦定每次只删当前点的出边。
然后可以注意到，在最优策略下，我们肯定不会走回重复的点：否则意味着出现了一个环，那么我们还是需要将这个环上的某条边删掉（否则最坏情况就是绕着环一直走），那么不如第一次走到的时候就删掉。
这意味着，我们删除某条边不会带来后效性，换言之最优策略中我只关心当前点在哪，并不关心我之前删了哪些边（因为我不可能走到一个重复的点）。
那么可以考虑设 \(f_u\) 表示当前点在 \(u\) 时，按最优策略走，最坏情况下到 \(n\) 所需的步数。
不妨假设所有 \(f\) 都已经求出来了，那么对于任意 \(u\neq n\)，将 \(u\) 的所有出点对应的 \(f\) 从小到大排序，设 \(rk_{u,v}\) 表示 \(v\) 排在第几位。
\[f_u=1+\min_{(u,v)\in E}(f_v+out_u-rk_{u,v}) \]而对于 \(u=n\)，应当有 \(f_n=0\)。
考虑如何求出 \(f\)，我们用类似 dijkstra 的方法。
归纳地假设对于任意 \(u\in S\)（\(S\) 是 \(\{1,\cdots,n\}\) 的子集）有 \(f_u\) 已经确定，且对于任意 \(u\in S,v\not\in S\) 有 \(f_u\leq f_v\)。初始时 \(S=\{n\}\)，且对于任意 \(v\not\in n\) 显然有 \(0=f_n\leq f_{v}\)。
对于任意 \(u\not\in S\)，将出点中属于 \(S\) 的那部分点对应的 \(f\) 排序（它们的 \(f\) 是已经确定了的），然后对于每个出点 \(v\) 满足 \(v\in S\) 定义 \(rk'_{u,v}\) 表示 \(v\) 排在第几位，那么根据归纳假设容易知道 \(rk'_{u,v}=rk_{u,v}\)。
设 \(f'_u=1+\min\limits_{(u,v)\in E,v\in S}(f_v+out_u-rk'_{u,v})\)，那么应有 \(f_u\leq f'_u\)。
设 \(M=\min\limits_{u\not\in S}f'_u\)，欲证明对于任意 \(u\not\in S\) 有 \(f_u\geq M\)。
取 \(u=\underset{u\not\in S}{\operatorname{argmin}}f_{u}\)，只需证明 \(f_u\geq M\) 即可。若 \(f_u<M\)，则应存在 \(v\not\in S\) 使得 \(f_u=1+f_v+out_u-rk_{u,v}>f_v\)，这与 \(f_u\) 是最小值矛盾。
取 \(u=\underset{u\not\in S}{\operatorname{argmin}}f'_{u}\)，刚刚我们得到了 \(f_u\geq f'_{u}\)，而又 \(f_u\leq f'_{u}\)，从而我们得到 \(f_u=f_u'\)。
那么我们可以将 \(u\) 加入 \(S\)，而且容易证明归纳假设成立。
其实这个问题和最短路很类似，但需要满足的方程中多了和 \(f_v\) 的排位有关，但 dijkstra 过程中这个东西我们已经求出来了，所以它不将带来什么影响。
标签：Search,min,geq,leq,dijkstra,Keshi,任意,rk From： https://www.cnblogs.com/ez-lcw/p/16837413.html