Official
H - Road Reduction Editorial by en_translator
Let \(D_i\) be the shortest distance from City \(1\) to City \(i\). No matter which roads are chosen, it obviously holds that \(d_i\geq D_i\), so if there is a way to choose roads so that \(d_i=D_i\), then that is the optimal solution. Actually, such a choice always exists.
It is sufficient to retain “the last road in the shortest path from City \(1\) to City \(i\)” for each \(i=2,3,\ldots,N\). We can prove that \(d_i=D_i\) are achieved by induction of the number of roads in the paths.
The answer can be found by recording the last road right before reaching each city during Dijkstra’s algorithm.