How Many Shortest Routes — Solution & Editorial

Back to the Problem

BFS layering plus path counting: reaching v at dist(u)+1 inherits ways(u); reaching it again on the same layer adds ways(u).

Complexity: O(N + M)