We are given an undirected connected graph G = (V, E) and vertices s and t. Initially, there is a robot at position s and we want to move this robot to position t by moving it along the edges of the graph; at any time step, we can move the robot to one of the neighboring vertices and the robot will reach that vertex in the next time step. However, we have a problem: at every time step, a subset of vertices of this graph undergo maintenance and if the robot is on one of these vertices at this time step, it will be destroyed (!). Luckily, we are given the schedule of the maintenance for the next T time steps in an array M [1 : T ], where each M [i] is a linked-list of the vertices that undergo maintenance at time step i. Design an algorithm that finds a route for the robot to go from s to t in at most T seconds so that at no time i, the robot is on one of the maintained vertices, or output that this is not possible. The runtime of your algorithm should ideally be O((n + m) ·T ) but you will receive partial credit for worse runtime also.
We are given an undirected connected graph G = (V, E) and vertices s and t.
Initially, there is a robot at position s and we want to move this robot to position t by moving it along the
edges of the graph; at any time step, we can move the robot to one of the neighboring vertices and the robot
will reach that vertex in the next time step.
However, we have a problem: at every time step, a subset of vertices of this graph undergo maintenance and
if the robot is on one of these vertices at this time step, it will be destroyed (!). Luckily, we are given the
schedule of the maintenance for the next T time steps in an array M [1 : T ], where each M [i] is a linked-list
of the vertices that undergo maintenance at time step i.
Design an
time i, the robot is on one of the maintained vertices, or output that this is not possible. The runtime of
your algorithm should ideally be O((n + m) ·T ) but you will receive partial credit for worse runtime also.
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
