3620. Network Recovery Pathways Hard

1/**
2 * [3620] Network Recovery Pathways
3 *
4 * <p data-end="502" data-start="75">You are given a directed acyclic graph of n nodes numbered from 0 to n - 1. This is represented by a 2D array <code data-end="201" data-start="194">edges of length<font face="monospace"> m</font>, where <code data-end="255" data-start="227">edges[i] = [ui, vi, costi] indicates a one‑way communication from node <code data-end="304" data-start="300">ui to node <code data-end="317" data-start="313">vi with a recovery cost of <code data-end="349" data-start="342">costi.
5 * <p data-end="502" data-start="75">Some nodes may be offline. You are given a boolean array <code data-end="416" data-start="408">online where <code data-end="441" data-start="423">online[i] = true means node <code data-end="456" data-start="453">i is online. Nodes 0 and n - 1 are always online.
6 * <p data-end="547" data-start="504">A path from 0 to n - 1 is <strong data-end="541" data-start="532">valid if:
7 * 
8 * 	All intermediate nodes on the path are online.
9 * 	<li data-end="676" data-start="605">The total recovery cost of all edges on the path does not exceed k.
10 * 
11 * <p data-end="771" data-start="653">For each valid path, define its <strong data-end="694" data-start="685">score as the minimum edge‑cost along that path.
12 * <p data-end="913" data-start="847">Return the maximum path score (i.e., the largest minimum-edge cost) among all valid paths. If no valid path exists, return -1.
13 *  
14 * <strong class="example">Example 1:
15 * <div class="example-block">
16 * Input: <span class="example-io">edges = [[0,1,5],[1,3,10],[0,2,3],[2,3,4]], online = [true,true,true,true], k = 10</span>
17 * Output: <span class="example-io">3</span>
18 * Explanation:
19 * <img alt="" src="https://assets.leetcode.com/uploads/2025/06/06/graph-10.png" style="width: 239px; height: 267px;" />
20 * <ul data-end="551" data-start="146">
21 * 	<li data-end="462" data-start="146">
22 * 	<p data-end="206" data-start="148">The graph has two possible routes from node 0 to node 3:
23 * 	<ol data-end="462" data-start="209">
24 * 		<li data-end="315" data-start="209">
25 * 		<p data-end="228" data-start="212">Path 0 &rarr; 1 &rarr; 3
26 * 		<ul data-end="315" data-start="234">
27 * 			<li data-end="315" data-start="234">
28 * 			<p data-end="315" data-start="236">Total cost = 5 + 10 = 15, which exceeds k (15 > 10), so this path is invalid.
29 * 			
30 * 		
31 * 		
32 * 		<li data-end="462" data-start="318">
33 * 		<p data-end="337" data-start="321">Path 0 &rarr; 2 &rarr; 3
34 * 		<ul data-end="462" data-start="343">
35 * 			<li data-end="397" data-start="343">
36 * 			<p data-end="397" data-start="345">Total cost = 3 + 4 = 7 <= k, so this path is valid.
37 * 			
38 * 			<li data-end="462" data-start="403">
39 * 			<p data-end="462" data-start="405">The minimum edge‐cost along this path is min(3, 4) = 3.
40 * 			
41 * 		
42 * 		
43 * 	</ol>
44 * 	
45 * 	<li data-end="551" data-start="463">
46 * 	<p data-end="551" data-start="465">There are no other valid paths. Hence, the maximum among all valid path‐scores is 3.
47 * 	
48 * </div>
49 * <strong class="example">Example 2:
50 * <div class="example-block">
51 * Input: <span class="example-io">edges = [[0,1,7],[1,4,5],[0,2,6],[2,3,6],[3,4,2],[2,4,6]], online = [true,true,true,false,true], k = 12</span>
52 * Output: <span class="example-io">6</span>
53 * Explanation:
54 * <img alt="" src="https://assets.leetcode.com/uploads/2025/06/06/graph-11.png" style="width: 343px; height: 194px;" />
55 * 
56 * 	<li data-end="790" data-start="726">
57 * 	<p data-end="790" data-start="728">Node 3 is offline, so any path passing through 3 is invalid.
58 * 	
59 * 	<li data-end="1231" data-start="791">
60 * 	<p data-end="837" data-start="793">Consider the remaining routes from 0 to 4:
61 * 	<ol data-end="1231" data-start="840">
62 * 		<li data-end="985" data-start="840">
63 * 		<p data-end="859" data-start="843">Path 0 &rarr; 1 &rarr; 4
64 * 		<ul data-end="985" data-start="865">
65 * 			<li data-end="920" data-start="865">
66 * 			<p data-end="920" data-start="867">Total cost = 7 + 5 = 12 <= k, so this path is valid.
67 * 			
68 * 			<li data-end="985" data-start="926">
69 * 			<p data-end="985" data-start="928">The minimum edge‐cost along this path is min(7, 5) = 5.
70 * 			
71 * 		
72 * 		
73 * 		<li data-end="1083" data-start="988">
74 * 		<p data-end="1011" data-start="991">Path 0 &rarr; 2 &rarr; 3 &rarr; 4
75 * 		<ul data-end="1083" data-start="1017">
76 * 			<li data-end="1083" data-start="1017">
77 * 			<p data-end="1083" data-start="1019">Node 3 is offline, so this path is invalid regardless of cost.
78 * 			
79 * 		
80 * 		
81 * 		<li data-end="1231" data-start="1086">
82 * 		<p data-end="1105" data-start="1089">Path 0 &rarr; 2 &rarr; 4
83 * 		<ul data-end="1231" data-start="1111">
84 * 			<li data-end="1166" data-start="1111">
85 * 			<p data-end="1166" data-start="1113">Total cost = 6 + 6 = 12 <= k, so this path is valid.
86 * 			
87 * 			<li data-end="1231" data-start="1172">
88 * 			<p data-end="1231" data-start="1174">The minimum edge‐cost along this path is min(6, 6) = 6.
89 * 			
90 * 		
91 * 		
92 * 	</ol>
93 * 	
94 * 	<li data-end="1314" data-is-last-node="" data-start="1232">
95 * 	<p data-end="1314" data-is-last-node="" data-start="1234">Among the two valid paths, their scores are 5 and 6. Therefore, the answer is 6.
96 * 	
97 * </div>
98 *  
99 * Constraints:
100 * 
101 * 	<li data-end="42" data-start="20"><code data-end="40" data-start="20">n == online.length
102 * 	<li data-end="63" data-start="45"><code data-end="61" data-start="45">2 <= n <= 5 * 10^4
103 * 	<li data-end="102" data-start="66"><code data-end="100" data-start="66">0 <= m == edges.length <= min(10^5, n * (n - 1) / 2)
104 * 	<li data-end="102" data-start="66"><code data-end="127" data-start="105">edges[i] = [ui, vi, costi]
105 * 	<li data-end="151" data-start="132"><code data-end="149" data-start="132">0 <= ui, vi < n
106 * 	<li data-end="166" data-start="154"><code data-end="164" data-start="154">ui != vi
107 * 	<li data-end="191" data-start="169"><code data-end="189" data-start="169">0 <= costi <= 10^9
108 * 	<li data-end="213" data-start="194"><code data-end="211" data-start="194">0 <= k <= 5 * 10^13
109 * 	<li data-end="309" data-start="216"><code data-end="227" data-start="216">online[i] is either <code data-end="244" data-is-only-node="" data-start="238">true or <code data-end="255" data-start="248">false, and both <code data-end="277" data-start="266">online[0] and <code data-end="295" data-start="282">online[n - 1] are <code data-end="306" data-start="300">true.
110 * 	<li data-end="362" data-is-last-node="" data-start="312">The given graph is a directed acyclic graph.
111 * 
112 */
113pub struct Solution {}
114
115// problem: https://leetcode.com/problems/network-recovery-pathways/
116// discuss: https://leetcode.com/problems/network-recovery-pathways/discuss/?currentPage=1&orderBy=most_votes&query=
117
118// submission codes start here
119
120impl Solution {
121    pub fn find_max_path_score(edges: Vec<Vec<i32>>, online: Vec<bool>, k: i64) -> i32 {
122        0
123    }
124}
125
126// submission codes end
127
128#[cfg(test)]
129mod tests {
130    use super::*;
131
132    #[test]
133    fn test_3620() {
134    }
135}
136