A museum's floor plan has rooms 0 .. n-1 joined by doors (every door works both ways). The information kiosk at the entrance prints a walking route to any room: the list of rooms to walk through, from the entrance to the room holding the exhibit you asked for, going through as few doors as possible.
Write museum_route(n, doors, entrance, exhibit) -> list[int]:
doorsis a list of pairs(a, b), each a door between roomsaandb. Doors may repeat, and a pair(a, a)may appear (a revolving door back into the same room).- Return the route as a list of rooms that starts with
entrance, ends withexhibit, has a door between every two consecutive rooms, and uses the fewest doors possible. If several routes are equally short, any of them is fine. - If
entrance == exhibit, the route is[entrance]. If the exhibit can't be reached, return[].
doors = [(0, 1), (1, 2), (2, 5), (0, 3), (3, 4), (4, 5), (1, 4), (6, 7)]
museum_route(8, doors, 0, 5) # [0, 1, 2, 5] or [0, 1, 4, 5] or [0, 3, 4, 5] (3 doors)
museum_route(8, doors, 0, 0) # [0]
museum_route(8, doors, 0, 7) # []
Constraints: 1 <= n <= 10**5, up to 2 * 10**5 doors. One test is a single corridor of 50,000 rooms, so rebuild the route with a loop, not recursion.
Show hint
run BFS from the entrance and, whenever you first reach a room, remember which room you came from (parent[v] = u). Then walk the parent links back from the exhibit to the entrance and reverse the list.