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)$ ~\mathcal O(N^2+NM+K)~

Comments

There are no comments at the moment.