Count the Shortest Routes
A transit map has n stops numbered 0 to n - 1. links is a list of pairs [a, b], each a link usable in both directions. No pair appears twice (in either order) and a != b.
A route is a sequence of stops in which consecutive stops are linked. Return how many different routes from source to goal use the fewest links possible; two routes are different when their sequences of stops differ. Return 1 when source == goal and 0 when goal cannot be reached.
Example 1
n 4
links [[0,1],[0,2],[1,3],[2,3]]
source 0
goal 3
returns 2
The shortest routes use 2 links: 0, 1, 3 and 0, 2, 3.
Example 2
n 3
links [[0,1],[1,2]]
source 0
goal 2
returns 1
The only route is 0, 1, 2.
Constraints
1 <= n <= 500 <= len(links) <= 100links[i] = [a, b]with0 <= a, b < nanda != b, no pair repeated0 <= source, goal < n
Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.
More Graphs problems
- Forced SidesMedium
- Largest PatchMedium
- Longest TrailMedium
- Lowest High PassMedium
- Mutual Reach GroupsMedium
- Nodes on a LoopMedium
- Rectangular IslandsMedium
- Rounds of Parallel JobsMedium