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