Skip to content

3543. Maximum Weighted K-Edge Path 👍

  • Time: $O(n^3k)$
  • Space: $O(n^2k)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
 public:
  int maxWeight(int n, vector<vector<int>>& edges, int k, int t) {
    vector<vector<pair<int, int>>> graph(n);
    // dp[u][i] := the set of possible path sums ending at node u with i edges
    vector<unordered_map<int, unordered_set<int>>> dp(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int w = edge[2];
      graph[u].emplace_back(v, w);
    }

    for (int u = 0; u < n; ++u)
      dp[u][0].insert(0);  // zero edges = sum 0

    for (int i = 0; i < k; ++i)
      for (int u = 0; u < n; ++u)
        if (dp[u].contains(i))
          for (const int currSum : dp[u][i])
            for (const auto& [v, w] : graph[u]) {
              const int newSum = currSum + w;
              if (newSum < t)
                dp[v][i + 1].insert(newSum);
            }

    int ans = -1;

    for (int u = 0; u < n; ++u)
      if (dp[u].contains(k))
        for (const int sum : dp[u][k])
          ans = max(ans, sum);

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
  public int maxWeight(int n, int[][] edges, int k, int t) {
    List<Pair<Integer, Integer>>[] graph = new List[n];
    // dp[i][j] := the set of possible path sums ending at node i with j edges
    Map<Integer, Set<Integer>>[] dp = new Map[n];

    for (int u = 0; u < n; ++u) {
      graph[u] = new ArrayList<>();
      dp[u] = new HashMap<>();
    }

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      final int w = edge[2];
      graph[u].add(new Pair<>(v, w));
    }

    for (int u = 0; u < n; ++u) {
      dp[u].putIfAbsent(0, new HashSet<>());
      dp[u].get(0).add(0); // zero edges = sum 0
    }

    for (int i = 0; i < k; ++i)
      for (int u = 0; u < n; ++u)
        if (dp[u].containsKey(i))
          for (final int currSum : dp[u].get(i))
            for (Pair<Integer, Integer> pair : graph[u]) {
              final int v = pair.getKey();
              final int w = pair.getValue();
              final int newSum = currSum + w;
              if (newSum < t) {
                dp[v].putIfAbsent(i + 1, new HashSet<>());
                dp[v].get(i + 1).add(newSum);
              }
            }

    int ans = -1;

    for (int u = 0; u < n; ++u)
      if (dp[u].containsKey(k))
        for (final int sum : dp[u].get(k))
          ans = Math.max(ans, sum);

    return ans;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
  def maxWeight(self, n: int, edges: list[list[int]], k: int, t: int) -> int:
    graph = [[] for _ in range(n)]
    # dp[u][i] := the set of possible path sums ending at node u with i edges
    dp = [defaultdict(set) for _ in range(n)]

    for u, v, w in edges:
      graph[u].append((v, w))

    for u in range(n):
      dp[u][0].add(0)  # zero edges = sum 0

    for i in range(k):
      for u in range(n):
        for currSum in dp[u][i]:
          for v, w in graph[u]:
            newSum = currSum + w
            if newSum < t:
              dp[v][i + 1].add(newSum)

    ans = -1

    for u in range(n):
      if k in dp[u]:
        ans = max(ans, max(dp[u][k]))

    return ans