Solve constrained monster traversal
Overview
This question evaluates proficiency in graph algorithms and resource-constrained pathfinding, focusing on state-space search, DFS with pruning, handling consumable resources and collectibles, and analysis of algorithmic complexity.
You are given a directed graph with n rooms labeled 0..n-1; each room i contains a monster with health hp[i] ≥ 0. You start at room s with energy E. Entering room i immediately reduces your energy by hp[i]; if energy ever becomes negative, you die. Part A: Determine whether there exists a path from s to target t such that energy never drops below 0 at any point; return true/false and one valid path if it exists. Implement using DFS with pruning and justify correctness and complexity. Part B: There are m potions; potion j sits in room pj and increases your energy by gain[j] the first time you enter pj. You may collect any potions along the way. Find a path from s to t that maximizes the number of rooms you can visit while keeping energy nonnegative, or report that t is unreachable. Discuss algorithmic approach (e.g., graph search with state, heuristics, or DP), correctness, and optimize for n up to 2e5 and edges up to 5e5.