## E - Subsequence Path Editorial by en_translator

Consider the following Dynamic Programming (DP).

The minimum sum of lengths of roads on the path from town \(1\) to \(u\) such that the indices of the used roads is a subsequence of \((E_1, \dots, E_i)\).

As \(i\) increases, we have more paths in which the sequence of indices of used roads is a subsequence of \((E_1, \dots, E_i)\). Considering \(i = k\) and \(i = k+1\), the new path is described by:

A path with \(i=k\) that ends at vertex \(A_{E_{k + 1}}\), succeeded by edge \(E_{k+1}\).

Therefore, the transition of DP is as follows:

First, initialize with \(\text{dp}[i + 1][u] :=\text{dp}[i][u]\).

Then, replace \(\text{dp}[i + 1][B_{E_{i + 1}}]\) with \(\min(\text{dp}[i + 1][B_{E_{i + 1}}], \text{dp}[i][A_{E_{i + 1}}] + C_{E_{i + 1}})\).

Computing it does not require an array of size \(NK\); we may prepare an array of length \(N\) and reuse as we update them in-place.

The complexity is \(O(N + M + K)\).

posted:

last update: