FunctionRacerProblemsRace

Count the Shortest Routes

MediumGraphsPython, JavaScript, TypeScript, Java, C++

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

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Graphs problems