Museum Exit Route with Dijkstra and Closed Rooms
A museum is preparing for a late-night event, but a few rooms are temporarily closed for maintenance. Visitors still need a valid walking route from one room to another, and each corridor has a travel cost based on distance and crowd control.
You are given the number of rooms, a list of two-way corridors in the form [u, v, cost], a start room, a destination room, and a list of closedRooms. A valid route may use only open rooms. If a room is closed, you are not allowed to enter it as part of the path.
The goal is to return the minimum total cost of an open route from the start room to the destination room. If the destination cannot be reached because every possible route passes through a closed room, return -1.
This is still a Dijkstra problem, but it adds an extra rule on top of the normal shortest-path search. You are not just minimizing cost anymore. You must also filter out rooms that are unavailable and make sure the algorithm never walks through them.
That extra condition is what makes this version a bit more interesting than the standard shortest-path template. The path with the smallest raw cost is not always legal once closures are taken into account.
Example Input & Output
The valid cheapest route is 0 -> 3 -> 4 -> 5 with total cost 6.
With no closures, the normal shortest path cost is 3.
Every possible route to room 3 uses a closed room, so the destination is unreachable.
Algorithm Flow
Solution Approach
The shortest-path part of this problem still belongs to Dijkstra's algorithm, because all corridor costs are non-negative and we still care about the minimum total route cost. The new twist is that some nodes are forbidden.
A practical approach is to place every closed room into a boolean array or hash set first. That way the algorithm can test in constant time whether a room is usable. If either the start room or the destination room is closed, you can immediately return -1 because no valid route can begin or end there.
After that, build the normal undirected adjacency list for the corridor graph. When Dijkstra explores neighbors, simply skip any neighbor that belongs to the closed-room set. That means the priority queue only ever receives legal next states.
The core idea looks like this:
This keeps the algorithm clean. You do not need a different shortest-path method; you only need to filter invalid rooms while performing the usual edge relaxations.
The runtime stays close to O((n + m) log n). The important lesson is that Dijkstra can still be used when the graph has extra movement rules, as long as those rules can be enforced while expanding states.
Best Answers
import java.util.*;
class Solution {
public int museum_exit_route_with_dijkstra(int n, int[][] corridors, int start, int destination, int[] closedRooms) {
boolean[] closed = new boolean[n];
for (int room : closedRooms) {
closed[room] = true;
}
if (closed[start] || closed[destination]) {
return -1;
}
List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
for (int[] corridor : corridors) {
graph.get(corridor[0]).add(new int[]{corridor[1], corridor[2]});
graph.get(corridor[1]).add(new int[]{corridor[0], corridor[2]});
}
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.offer(new int[]{0, start});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int cost = current[0];
int node = current[1];
if (node == destination) {
return cost;
}
if (cost > dist[node]) {
continue;
}
for (int[] edge : graph.get(node)) {
int next = edge[0];
if (closed[next]) {
continue;
}
int candidate = cost + edge[1];
if (candidate < dist[next]) {
dist[next] = candidate;
pq.offer(new int[]{candidate, next});
}
}
}
return -1;
}
}Comments (0)
Join the Discussion
Share your thoughts, ask questions, or help others with this Challenge.