Here, to find the required the shortest distance from u to v, you will need the shortest distance from any u to C and then C to any v.

The later part can be precomputed by a single BFS from source C.

The first part might seem a little bit tricky, but it can also be done by a single BFS from source C in the reversed graph.


75% Solution Ratio
UnseenEarliest, Dec '16
Mestu_PaulFastest, 0.0s
Mestu_PaulLightest, 9.4 kB
mumith_fahim99Shortest, 945B
Toph uses cookies. By continuing you agree to our Cookie Policy.