Medium

Maximum Weighted K-Edge Path

LAB

Given directed weighted edges [u,v,w], return the maximum path weight using exactly k edges, or -1 if none exists.

EXAMPLES

Example 1

Input
{
  "n": 3,
  "edges": [
    [
      0,
      1,
      5
    ],
    [
      1,
      2,
      7
    ],
    [
      0,
      2,
      3
    ]
  ],
  "k": 2
}

Output
12

FUNCTION SHAPE

n: intedges: intMatrixk: int→int

SOLUTION NOTE

Track all possible sums for paths of length k from each node. Use set to collect valid sums < t.

Reveal reference solution +

pythonREFERENCE

def maxWeight(self, n: int, edges: List[List[int]], k: int, t: int) -> int:
    adjList = defaultdict(list)
    for u, v, w in edges:
        adjList[u].append((v, w))

    @cache
    def dp(i, k):
        if k == 0: return {0}
        res = set()
        for nbr, w in adjList[i]:
            for nbr_sum in dp(nbr, k - 1):
                if w + nbr_sum < t:
                    res.add(w + nbr_sum)
        return res

    res = -1
    for i in range(n):
        for path_sum in dp(i, k):
            if path_sum < t:
                res = max(res, path_sum)
    return res

TimeO(E × k × t)

SpaceO(n × k × t)

Open on LeetCode ↗