3543. Maximum Weighted K-Edge Path Medium

1/**
2 * [3543] Maximum Weighted K-Edge Path
3 *
4 * You are given an integer n and a Directed Acyclic Graph (DAG) with n nodes labeled from 0 to n - 1. This is represented by a 2D array edges, where edges[i] = [ui, vi, wi] indicates a directed edge from node ui to vi with weight wi.
5 * You are also given two integers, k and t.
6 * Your task is to determine the maximum possible sum of edge weights for any path in the graph such that:
7 * 
8 * 	The path contains exactly k edges.
9 * 	The total sum of edge weights in the path is strictly less than t.
10 * 
11 * Return the maximum possible sum of weights for such a path. If no such path exists, return -1.
12 *  
13 * <strong class="example">Example 1:
14 * <div class="example-block">
15 * Input: <span class="example-io">n = 3, edges = [[0,1,1],[1,2,2]], k = 2, t = 4</span>
16 * Output: <span class="example-io">3</span>
17 * Explanation:
18 * <img src="https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-061326.png" style="width: 180px; height: 162px;" />
19 * 
20 * 	The only path with k = 2 edges is 0 -> 1 -> 2 with weight 1 + 2 = 3 < t.
21 * 	Thus, the maximum possible sum of weights less than t is 3.
22 * </div>
23 * <strong class="example">Example 2:
24 * <div class="example-block">
25 * Input: <span class="example-io">n = 3, edges = [[0,1,2],[0,2,3]], k = 1, t = 3</span>
26 * Output: <span class="example-io">2</span>
27 * Explanation:
28 * <img src="https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-061406.png" style="width: 180px; height: 164px;" />
29 * 
30 * 	There are two paths with k = 1 edge:
31 * 	
32 * 		0 -> 1 with weight 2 < t.
33 * 		0 -> 2 with weight 3 = t, which is not strictly less than t.
34 * 	
35 * 	
36 * 	Thus, the maximum possible sum of weights less than t is 2.
37 * </div>
38 * <strong class="example">Example 3:
39 * <div class="example-block">
40 * Input: <span class="example-io">n = 3, edges = [[0,1,6],[1,2,8]], k = 1, t = 6</span>
41 * Output: <span class="example-io">-1</span>
42 * Explanation:
43 * <img src="https://assets.leetcode.com/uploads/2025/04/09/screenshot-2025-04-10-at-061442.png" style="width: 180px; height: 154px;" />
44 * 
45 * 	There are two paths with k = 1 edge:
46 * 	
47 * 		0 -> 1 with weight 6 = t, which is not strictly less than t.
48 * 		1 -> 2 with weight 8 > t, which is not strictly less than t.
49 * 	
50 * 	
51 * 	Since there is no path with sum of weights strictly less than t, the answer is -1.
52 * </div>
53 *  
54 * Constraints:
55 * 
56 * 	1 <= n <= 300
57 * 	0 <= edges.length <= 300
58 * 	edges[i] = [ui, vi, wi]
59 * 	0 <= ui, vi < n
60 * 	ui != vi
61 * 	1 <= wi <= 10
62 * 	0 <= k <= 300
63 * 	1 <= t <= 600
64 * 	The input graph is guaranteed to be a DAG.
65 * 	There are no duplicate edges.
66 * 
67 */
68pub struct Solution {}
69
70// problem: https://leetcode.com/problems/maximum-weighted-k-edge-path/
71// discuss: https://leetcode.com/problems/maximum-weighted-k-edge-path/discuss/?currentPage=1&orderBy=most_votes&query=
72
73// submission codes start here
74
75impl Solution {
76    pub fn max_weight(n: i32, edges: Vec<Vec<i32>>, k: i32, t: i32) -> i32 {
77        0
78    }
79}
80
81// submission codes end
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    #[test]
88    fn test_3543() {
89    }
90}
91