Editorial for DMOPC '14 Contest 5 P5 - Attack on Anti-Spiral
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.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
The given graph is a cactus graph. There are at most two edge-disjoint paths between any pair of vertices (proof is left as an exercise to the reader). For each vertex, we will store the distances of these two paths (with one being as short as possible), and use dynamic programming to fill in the other vertices.
Time Complexity:
Comments