Contest Duration: - (local time) (100 minutes) Back to Home
Official

## 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)$$.

Sample code (C++)

posted:
last update: