答えで二分探索して，「頂点 \(1\) から頂点 \(N\) への最短距離を \(d\) 以上にできるか？」という判定問題を考えます．最短距離を \(d\) 以上にするために変更する必要がある最小の辺の本数が求められれば，それと \(K\) の大小関係を見ることで判定問題を解けます．

\(d=1\) の場合

まず，簡単な場合として \(d=1\) の場合を考えます．このとき，変更する必要がある最小の辺の本数は，元のグラフにおける頂点 \(1,N\) 間の最小カットの大きさに一致します．なぜならば，「最短距離が \(1\) 以上」 \(\Leftrightarrow\) 「重みが \(0\) の辺のみを通って頂点 \(N\) に到達できない」ですので，重みが \(1\) の辺を切ることにすれば，頂点 \(1\) から \(N\) に到達できないようにするために削除する必要のある最小の辺の本数が答えになるからです．

頂点数 \(N\), 辺数 \(M\) のグラフで Dinic のアルゴリズムを用いて最小カットを求めた場合，最小カットの重みを \(F\) として時間計算量は \(O(F(N+M))\) です．今回 \(F \leq M\) なのでこれは \(O(M(N+M))\) です．（計算量については AtCoder Library のドキュメントも参照してください）

次節の準備のため，このことを少し抽象的に言い換えます．\(0,1\) の値を取る \(N\) 個の変数 \(x_i \; (i=1,\dots,N)\) を考えます．\(x_i\) は頂点 \(1\) から頂点 \(i\) への最短距離を表します．そして，各辺 \((u,v)\) について，\(x_u=0\) かつ \(x_v=1\) のときに，そしてそのときに限りコスト \(1\) がかかるとします．問題は，「\(x_1,\dots,x_N\) への値の割当であって，\(x_1=0,x_N=1\) を満たすもののうち，コストの総和が最小になるものはなにか？」という問題になります．このような問題は俗に「燃やす埋める問題」と呼ばれ，最小カットにより解くことができます．

一般の \(d\) の場合

一般の \(d\) の場合を考えます．\(d=1\) の場合と同様に考えて，\(0,1,\dots,d\) の値を取る \(N\) 個の変数 \(x_i \; (i=1,\dots,N)\) を考えます．\(x_i\) は頂点 \(1\) から頂点 \(i\) への最短距離を表します．各辺 \((u,v)\) について，コストを以下のように定めます：

• \(x_u+1=x_v\) のとき：コスト \(1\)
• \(x_u+1<x_v\) のとき：コスト \(\infty\)　（\(u\) への最短距離が \(x_u\) ならば，\(v\) への最短距離は \(x_u+1\) より大きくなることがないため）

問題は，「\(x_1,\dots,x_N\) への値の割当であって，\(x_1=0,x_N=d\) を満たすもののうち，コストの総和が最小になるものはなにか？」という問題になります．これを最小カットに帰着するために，変数が \(0,1\) の値を取るように問題を変形します．

\(0,1\) の値を取る \(Nd\) 個の変数 \(y_{i,j} \; (i=1,\dots,N,j=1,\dots,d)\) を考えます．\(x_i\) と \(y_{i,1}, \dots, y_{i,d}\) を以下のように対応させます．

• \(x_i = j \Leftrightarrow y_{i,1}=\dots=y_{i,j}=1,y_{i,j+1}=\dots,y_{i,d}=0\)

ある \(y_{i,j}\) が \(0\) となれば，\(y_{i,j+1},\dots,y_{i,d}\) も \(0\) となる必要があるため，各 \(i=1,\dots,N, \,j=1,\dots,d-1\) について，以下のコストを定めます．

• \(y_{i,j}=0\) かつ \(y_{i,j+1}=1\) のとき：コスト \(\infty\)

また，\(x\) に関するコストを \(y\) に関するコストに言い換えると次のようになります．

• \(y_{u,j}=0\) かつ \(y_{v,j}=1\) のとき \((j=1,\dots,d)\)：コスト \(1\)
• \(y_{u,j}=0\) かつ \(y_{v,j+1}=1\) のとき \((j=1,\dots,d-1)\)：コスト \(\infty\)

以上のコストの設定のもとで，\(y_{1,1}=0,y_{N,d}=1\) となるように各変数に値を割り当ててコストを最小化すればよいです．これは，頂点数 \(Nd\), 辺数 \(N(d-1)+M(2d-1)\) のグラフにおける最小カットにより解くことができます．\(d\) はたかだか \(N-1\) であり，最小カットの重みはたかだか \(M\) なので，二分探索と合わせて全体の時間計算量は \(O((N+M) MN \log N)\) となります．