次のような動的計画法を考えます。

\(\text{dp}[i][u] :=\) 都市 \(1\) から都市 \(u\) へ行く経路であって、通る道の番号を並べた列が \((E_1, \dots, E_i)\) の部分列になるようなものに対する、通る道の長さの合計の最小値。

\(i\) が大きくなるにつれて、通る道の番号を並べた列が \((E_1, \dots, E_i)\) の部分列になるような経路は増えていきます。\(i = k\) のときと \(i = k+1\) のときを比較すると、新たに次のような経路が増えます。

\(i=k\) のときの経路であって、頂点 \(A_{E_{k + 1}}\) を終端とするものを考える。このような経路において、さらに辺 \(E_{k+1}\) を通ったような経路。

よって、動的計画法の遷移は次のようにすればよいです。

まず、\(\text{dp}[i + 1][u] :=\text{dp}[i][u]\) と初期化する。

次に、\(\text{dp}[i + 1][B_{E_{i + 1}}]\) を \(\min(\text{dp}[i + 1][B_{E_{i + 1}}], \text{dp}[i][A_{E_{i + 1}}] + C_{E_{i + 1}})\) で置き換える。

これを計算するのに大きさ \(NK\) の配列を用意する必要はありません。大きさ \(N\) の配列を用意し、それを使い回して in-place に更新することができます。
計算量は \(O(N + M + K)\) です。

実装例 (C++)