## 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 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: