Best Recovery Score Within a Path Budget

# Best Recovery Score Within a Path Budget You are given a directed acyclic graph with nodes `0` through `n - 1`. Each entry `[u, v, cost]` in `edges` is a directed edge from `u` to `v` with that recovery cost. The boolean array `online` indicates which nodes are available; nodes zero and `n - 1` are always online. A path from node zero to node `n - 1` is valid when all its intermediate nodes are online and the sum of its edge costs is at most `k`. The score of a valid path is its minimum edge cost. Return the largest score among all valid paths. Return `-1` if there is no valid path. ### C++ Interface ```cpp class Solution { public: int findMaxPathScore(vector<vector<int>>& edges, vector<bool>& online, long long k); }; ``` The number of nodes is `online.size()`. ### Examples **Example 1** ```text edges = [[0,3,7],[3,1,5],[1,4,5],[0,2,6],[2,4,6]] online = [true,true,true,true,true] k = 17 Output: 6 ``` There are two source-to-destination paths. Path `0 -> 3 -> 1 -> 4` costs seventeen and scores five. Path `0 -> 2 -> 4` costs twelve and scores six. Both satisfy the budget, and six is the larger score. **Example 2** ```text edges = [[0,1,9],[1,3,9],[0,2,0],[2,3,0]] online = [true,false,true,true] k = 0 Output: 0 ``` The route through node one is unavailable because that intermediate node is offline. Path `0 -> 2 -> 3` is online, has total cost zero, and has score zero. A valid zero score is returned as zero, not `-1`. ### Constraints - `n == online.length` and `2 <= n <= 50000`. - `0 <= edges.length <= min(100000, n * (n - 1) / 2)`. - Each edge is `[u, v, cost]`, where `0 <= u, v < n` and `u != v`. - `0 <= cost <= 1000000000`. - `0 <= k <= 50000000000000`. - Every `online[i]` is boolean, and the two endpoints are online. - The graph is directed and acyclic. ### Clarifying Questions - Is a path's score its total cost? No. The total cost is the budgeted quantity; the score is the smallest cost of one of its edges. - May a path pass through an offline node? No. Its intermediate nodes must all be online. - Can an edge have cost zero? Yes. A valid path containing it has score zero. - Are node labels guaranteed to follow edge direction? No. Acyclicity does not require `u < v`. - Must a path exist? No. Disconnected or unaffordable cases return `-1`. ### What a Strong Answer Covers - The two distinct path quantities: total recovery cost and minimum edge score. - Correct direction and availability checks for every used edge and intermediate node. - Correct distinction between a valid zero score and no valid path. - Safe arithmetic and resource bounds for 50000 nodes, 100000 edges, and the stated large budget. ### Follow-up Questions - Can increasing the budget make the best available score smaller? - Does an offline node matter when it is not used by the selected path? ```hint Check a candidate score For a proposed score T, keep only online-node edges with cost at least T. Ask whether the minimum total cost from zero to n-1 in that filtered DAG fits the budget. Feasibility is monotone in T, and any path's minimum cost is one of the listed edge costs. ```