Skip to content

2247. Maximum Cost of Trip With K Highways 👍

  • Time: $O(n^2 \cdot 2^n + |\texttt{highways}|)$
  • Space: $O(n \cdot 2^n + |\texttt{highways}|)$
 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
class Solution {
 public:
  int maximumCost(int n, vector<vector<int>>& highways, int k) {
    if (k + 1 > n)
      return -1;

    int ans = -1;
    vector<vector<int>> mem(n, vector<int>(1 << n, -1));
    vector<vector<pair<int, int>>> graph(n);

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

    for (int i = 0; i < n; ++i)
      ans = max(ans, maximumCost(graph, i, 1 << i, k, mem));

    return ans;
  }

 private:
  // Returns the maximum cost of trip starting from u, where `mask` is the
  // bitmask of the visited cities.
  int maximumCost(const vector<vector<pair<int, int>>>& graph, int u,
                  unsigned mask, int k, vector<vector<int>>& mem) {
    if (popcount(mask) == k + 1)
      return 0;
    if (mem[u][mask] != -1)
      return mem[u][mask];

    int res = -1;
    for (const auto& [v, w] : graph[u]) {
      if (mask >> v & 1)
        continue;
      const int nextCost = maximumCost(graph, v, mask | 1 << v, k, mem);
      if (nextCost != -1)
        res = max(res, w + nextCost);
    }

    return mem[u][mask] = res;
  }
};

 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
48
49
class Solution {
  public int maximumCost(int n, int[][] highways, int k) {
    if (k + 1 > n)
      return -1;

    int ans = -1;
    Integer[][] mem = new Integer[n][1 << n];
    List<Pair<Integer, Integer>>[] graph = new List[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

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

    for (int i = 0; i < n; ++i)
      ans = Math.max(ans, maximumCost(graph, i, 1 << i, k, mem));

    return ans;
  }

  // Returns the maximum cost of trip starting from u, where `mask` is the
  // bitmask of the visited cities.
  private int maximumCost(List<Pair<Integer, Integer>>[] graph, int u, int mask, int k,
                          Integer[][] mem) {
    if (Integer.bitCount(mask) == k + 1)
      return 0;
    if (mem[u][mask] != null)
      return mem[u][mask];

    int res = -1;
    for (Pair<Integer, Integer> pair : graph[u]) {
      final int v = pair.getKey();
      final int w = pair.getValue();
      if ((mask >> v & 1) == 1)
        continue;
      final int nextCost = maximumCost(graph, v, mask | 1 << v, k, mem);
      if (nextCost != -1)
        res = Math.max(res, w + nextCost);
    }

    return mem[u][mask] = res;
  }
}

 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
class Solution:
  def maximumCost(self, n: int, highways: list[list[int]], k: int) -> int:
    if k + 1 > n:
      return -1

    graph = [[] for _ in range(n)]

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

    @functools.lru_cache(None)
    def dp(u: int, mask: int) -> int:
      """
      Returns the maximum cost of trip starting from u, where `mask` is the
      bitmask of the visited cities.
      """
      if mask.bit_count() == k + 1:
        return 0

      res = -1
      for v, w in graph[u]:
        if mask >> v & 1:
          continue
        nextCost = dp(v, mask | 1 << v)
        if nextCost != -1:
          res = max(res, w + nextCost)
      return res

    return max(dp(i, 1 << i) for i in range(n))