Editorial for CIW '26 P1 - Shopping Mall - Olympiads Online Judge

Editorial for CIW '26 P1 - Shopping Mall

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Kirito

We can construct a graph with $N\times(K+1)$ ~N\times(K+1)~ vertices and $KM$ ~KM~ vertices. Intuitively, the vertex $(v, k)$ ~(v, k)~ corresponds to reaching vertex $k$ ~k~ having bought items $1, 2, \ldots, k$ ~1, 2, \ldots, k~.

To construct the graph, we add the directed edge $(u,k)\to(v,k)$ ~(u,k)\to(v,k)~ if and only if $uv$ ~uv~ is an edge of the input, and store $v$ ~v~ does not sell item $k+1$ ~k+1~. Otherwise, if $uv$ ~uv~ is an edge of the input, and store $v$ ~v~ does sell item $k+1$ ~k+1~, we add the edge $(u,k)\to(v,k+1)$ ~(u,k)\to(v,k+1)~ instead.

Finally, running a multisource BFS, we return the shortest distance to any vertex $(v,K)$ ~(v,K)~.

Comments

There are no comments at the moment.