PreviousNext
Coding/Graphs and trees

Shortest path count modulo

Write codeMedium30 min

Your task

Given an unweighted undirected graph with n nodes (0..n-1) and edges [u, v], return the number of distinct shortest paths from a source to a destination, taken modulo 1000000007. If the destination is unreachable, return 0; if source equals destination, return 1. Constraints: 1 <= n <= 2000.

Examples

count_shortest_paths(n: int, edges: list[list[int]], src: int, dst: int) -> int
Example 1
Inputcount_shortest_paths(4, [[0, 1], [0, 2], [1, 3], [2, 3]], 0, 3)
Output2