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

**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 be the shortest path from node to node without using any new edges. Let be the shortest path from to using at most new edge, which ends at node . Any shortest path from node to node using at most new edges can be written as .

First assume that all colors are different. Find the shortest path between all nodes to precalculate all . Notice that an edge from to can change into if that edge is used. Thus, loop over all edges to precompute all . Use the same logic to precompute all . Then loop over all pairs and store the minimum distance .

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

Time complexity:

## Comments