How Many Shortest Routes

Difficulty: 1700 4000 ms 128 MB

bfs graphs

Count the distinct shortest (fewest-hop) routes from node 1 to node N, modulo 10⁹+7 (0 if unreachable).

Input: the first line has N and M; each of the next M lines has an edge u v (1-based).

Output: the number of shortest routes mod 10⁹+7.

Constraints:

• 2 ≤ N ≤ 10⁴
• 0 ≤ M ≤ 2×10⁴

Sample Tests

4 4
1 2
1 3
2 4
3 4

2

2 0

0

Read the Editorial