FunctionRacerProblemsRace

Through the Checkpoint

MediumGraphsPython, JavaScript, TypeScript, Java, C++

A forest has n clearings numbered 0 to n - 1. paths is a list of pairs [a, b] with a != b, each a path that can be walked in both directions; the same pair may appear more than once. A hike starts at clearing start, must stand in clearing checkpoint at some point, and ends at clearing goal. Any of these three may be the same clearing, and the hike may walk a path or enter a clearing more than once.

Return the fewest paths walked on such a hike, or -1 if no such hike exists.

Example 1

n 5
paths [[0,1],[1,2],[2,3],[3,4],[0,4]]
start 0
checkpoint 2
goal 4
returns 4

Two paths take you from 0 to 2, and two more from 2 to 4; the direct path [0, 4] skips the checkpoint, so it does not help.

Example 2

n 4
paths [[0,1],[2,3]]
start 0
checkpoint 1
goal 3
returns -1

The checkpoint 1 can be reached from 0, but 3 is cut off from both.

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