まず、頂点\(1\)から頂点\(N\)までの最短パスの長さがある整数\(K\)以下である（そうでないなら到達不可能である）ことがわかっていれば、ABC212-Eと同様にして\(\Omicron((N+M)K)\)で問題を解くことができます。よって、最短パスの長さのよい上界を見つけることができれば高速にこの問題を解くことができます。

ここで、頂点\(1\)から頂点\(N\)まで到達可能であるとき、頂点\(1\)から頂点\(N\)までの最短パスをひとつとり、最短パスの長さを\(d\)としてその最短パスを頂点列\((V_0,V_1,\ldots,V_d)\)で表すことにします。すると、最短パスの最短性より、任意の\(|i-j|\geq2\)をみたす組\((i,j)\)について、頂点\(V_i\)と頂点\(V_j\)の間には辺が存在しないため、最短パスの長さが\(d\)であるためには少なくとも\(\displaystyle{\frac{d(d-1)}{2}}\)本の辺が削除されている必要があります。

よって、\(\displaystyle{\frac{d(d-1)}{2}}\leq M\)より、\(d=\Omicron(\sqrt{M})\)であるため、\(\Omicron((N+M)\sqrt{M})\)でこの問題を解くことができます。