Library Courtesy Door Route
Lexicographically smallest shortest graph path using at most one marked edge
A library has rooms numbered from 0 to n - 1. Its passages are one-way. Each passage is either public or a courtesy door that visitors may use only with a special pass.
You have one pass, which allows you to traverse at most one courtesy door during the entire route. Public passages can be traversed without spending the pass.
Each entry [u, v, kind] in passages describes a passage from room u to room v. A kind of 0 means a public passage, and a kind of 1 means a courtesy door.
Return the sequence of room numbers for a route from start to finish that traverses the fewest passages while respecting the pass limit. If several shortest routes exist, return the lexicographically smallest room sequence: at the first differing position, the route with the smaller room number wins.
Return an empty list if no valid route exists. If start == finish, return [start]. Rooms may be revisited, provided the pass limit is respected.
Examples
Example 1
Input: n = 5, passages = [[0,2,0],[2,4,0],[0,1,1],[1,4,0]], start = 0, finish = 4 Output: [0,1,4]
Both 0 → 1 → 4 and 0 → 2 → 4 use two passages and respect the pass limit. The route through room 1 is lexicographically smaller, even though it spends the pass.
Example 2
Input: n = 3, passages = [[0,1,1],[1,2,1]], start = 0, finish = 2 Output: []
The only route from room 0 to room 2 crosses two courtesy doors, so it is not permitted.
Example 3
Input: n = 3, passages = [[1,2,1]], start = 1, finish = 1 Output: [1]
The visitor is already in the destination room, so no passage needs to be traversed.
Constraints
- 1 <= n <= 20000
- 0 <= passages.length <= 20000
- Each passage is [u, v, kind], where 0 <= u, v < n, u != v, and kind is either 0 or 1.
- There is at most one passage for each ordered pair (u, v).
- 0 <= start, finish < n
The intended solution runs in O(n + passages.length) time and space. Lexicographic order is applied to room numbers as integers, not to their string representations.
Hints
Show hint 1Hint 1
A room alone does not describe your situation: also record whether the pass has already been spent.
Show hint 2Hint 2
Compute distances to the destination in the reversed state graph. During reconstruction, choose the smallest next room that reduces the remaining distance by one.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would the algorithm change if the visitor could use up to k courtesy doors?
- How would you find only the minimum travel time if passages had nonnegative travel times instead of equal cost?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem