G - Road Blocked 2 Editorial by LinLeXiao
Alternative SolutionIt’s easy to calculate the number of different shortest paths from a certain starting point using Dijkstra.
Let’s say \(cnt1_i\) represents the number of different shortest paths from vertex \(1\) to vertex \(i\), and \(d1_i\) represents the minimal distance from vertex \(1\) to vertex \(i\).
Similarly, let \(cnt2_i\) represent the number of different shortest paths from vertex \(n\) to vertex \(i\), and \(d2_i\) represent the minimal distance from vertex \(n\) to vertex \(i\).
A key insight is that, for a bidirectional edge \((u,v)\) with weight \(w\), if the number of shortest path from \(1\) to \(n\) that pass \((u,v)\) equals \(cnt1_n\) implies all shortest paths include this edge, thus the answer is Yes
.
Specifically, the answer for such an edge is Yes
if either of the following holds:
\(d1_u + d2_v + w = d1_n\) and \(cnt1_u \times cnt2_v = cnt1_n\)
\(d1_v + d2_u + w = d1_n\) and \(cnt1_v \times cnt2_u = cnt1_n\)
The only problem is that the number of different shortest paths may be too large to store. To solve this, use multi-hashing, and the problem can be easily solved.
posted:
last update: