Editorial for WOSS Dual Olympiad 2023 Team Round P3: Choosing Edges

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.

Let $(a, b)$ $(a, b)$ be the shortest path from node $a$ $a$ to node $b$ $b$ without using any new edges. Let $(a, b, 1)$ $(a, b, 1)$ be the shortest path from $a$ $a$ to $b$ $b$ using at most $1$ $1$ new edge, which ends at node $b$ $b$ . Any shortest path from node $1$ $1$ to node $N$ $N$ using at most $2$ $2$ new edges can be written as $(1, a, 1)+(a, b)+(b, N, 1)$ $(1, a, 1) + (a, b) + (b, N, 1)$ .

First assume that all colors are different. Find the shortest path between all nodes to precalculate all $(a, b)$ $(a, b)$ . Notice that an edge from $u_i$ $u_{i}$ to $v_i$ $v_{i}$ can change $(1, v_i, 1)$ $(1, v_{i}, 1)$ into $(1, u_i)+1$ $(1, u_{i}) + 1$ if that edge is used. Thus, loop over all edges to precompute all $(1, a, 1)$ $(1, a, 1)$ . Use the same logic to precompute all $(a, N, 1)$ $(a, N, 1)$ . Then loop over all pairs $(a, b)$ $(a, b)$ and store the minimum distance $(1, a, 1)+(a, b)+(b, N, 1)$ $(1, a, 1) + (a, b) + (b, N, 1)$ .

This can be easily modified to account for colors. Store $2$ $2$ values of each $(1, a, 1)$ $(1, a, 1)$ : The minimum distance, and the minimum distance using a different colored edge than the first minimum distance. Do some casework when looping over all pairs $(a, b)$ $(a, b)$ to ensure that the same colored edges are not used.

Time complexity: $\mathcal O(N^2+NM+K)$ $O (N^{2} + N M + K)$

Comments

There are no comments at the moment.