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) be the shortest path from node a to node b without using any new edges. Let (a, b, 1) be the shortest path from a to b using at most 1 new edge, which ends at node b. Any shortest path from node 1 to node N using at most 2 new edges can be written as (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). Notice that an edge from u_i to v_i can change (1, v_i, 1) into (1, u_i)+1 if that edge is used. Thus, loop over all edges to precompute all (1, a, 1). Use the same logic to precompute all (a, N, 1). Then loop over all pairs (a, b) and store the minimum distance (1, a, 1)+(a, b)+(b, N, 1).

This can be easily modified to account for colors. Store 2 values of each (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) to ensure that the same colored edges are not used.

Time complexity: \mathcal O(N^2+NM+K)


There are no comments at the moment.