3543. Maximum Weighted K-Edge Path

Problem Link

Description

---

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.

You are also given two integers, k and t.

Your task is to determine the maximum possible sum of edge weights for any path in the graph such that:

• The path contains exactly k edges.
• The total sum of edge weights in the path is strictly less than t.

Return the maximum possible sum of weights for such a path. If no such path exists, return -1.

 

Example 1:

Input: n = 3, edges = [[0,1,1],[1,2,2]], k = 2, t = 4

Output: 3

Explanation:

• The only path with k = 2 edges is 0 -> 1 -> 2 with weight 1 + 2 = 3 < t.
• Thus, the maximum possible sum of weights less than t is 3.

Example 2:

Input: n = 3, edges = [[0,1,2],[0,2,3]], k = 1, t = 3

Output: 2

Explanation:

• There are two paths with k = 1 edge:

  <ul>
  	<li><code>0 -&gt; 1</code> with weight <code>2 &lt; t</code>.</li>
  	<li><code>0 -&gt; 2</code> with weight <code>3 = t</code>, which is not strictly less than <code>t</code>.</li>
  </ul>
  </li>
  <li>Thus, the maximum possible sum of weights less than <code>t</code> is 2.</li>
  

Example 3:

Input: n = 3, edges = [[0,1,6],[1,2,8]], k = 1, t = 6

Output: -1

Explanation:

• There are two paths with k = 1 edge:
  • 0 -> 1 with weight 6 = t, which is not strictly less than t.
  • 1 -> 2 with weight 8 > t, which is not strictly less than t.
• Since there is no path with sum of weights strictly less than t, the answer is -1.

 

Constraints:

• 1 <= n <= 300
• 0 <= edges.length <= 300
• edges[i] = [ui, vi, wi]
• 0 <= ui, vi < n
• ui != vi
• 1 <= wi <= 10
• 0 <= k <= 300
• 1 <= t <= 600
• The input graph is guaranteed to be a DAG.
• There are no duplicate edges.

Solution

---

Python3

class Solution:
    def maxWeight(self, n: int, edges: List[List[int]], K: int, T: int) -> int:
        graph = defaultdict(list)
        topo = []
 
        for u, v, w in edges:
            graph[u].append((v, w))
        
        @cache
        def dp(node, k, t):
            if k == K: return t
 
            res = -inf
            for adj, w in graph[node]:
                if t + w < T:
                    res = max(res, dp(adj, k + 1, t + w))
            
            return res
        
        ans = -inf
 
        for node in range(n):
            ans = max(ans, dp(node, 0, 0))
        
        if ans == -inf: return -1
 
        return ans