DATA structures challenging question

POST RESOLVED THANKS FOR YOUR COOPERATION

Why we are giving 35 to 2nd worker as when we have minimize we can take 30 which is valid for question?

Because when you pay to the guy with skill 10 it will be 60 which is less than 70.

@codedirector can u help in solving this question. i am not able to do it

@sayan_244 Can u help in solving this question . i am not able to solve this and understand how to proceed in it. please help i want to know how to solve this . please solve this using java as i am more familiar with java.

This one requires you to use dfs.
So for the path which is blocked you iterate through the list of paths and mark either of the connecting doors as visited and run a dfs from R and check if E is visited after dfs. (If it is then he can escape else he cannot)

The dfs you run should have a distance parameter too which will include the distance of every other node from R. (It’s possible to do it as its a tree). The distance will be a sum of the tunnel length at every step and pass it to next node. (simply like how its done in normal dfs and depth added parameter)

So in total you have to do this:-
Run dfs with depth parameter from R. (Make either of the node on the blocked tunnel as visited)

  1. Check if E is visited after dfs.
  2. If first condition doesn’t hold check if atleast one of the supply nodes is visited.
  3. If 2nd condition holds simply take minimum of distances from supply nodes.

constraints are small enough so we can easily run a dfs every query.

The previous question I wasn’t able to solve. My friend happens to be from the same college as yours.

@ thanks for the help. can u suggest a way through which it can be done in O(logn) time

Kindly share the code

Please help!!!


Why do you have 2 posts with the same Question?
I have alrrady explained how to solve queries in O(\log{n})

@everule1 considering the constraints of the question. Does my solution hold correct?