Question

2247. Maximum Cost of Trip With K Highways

中文文档

Description

A series of highways connect n cities numbered from 0 to n - 1. You are given a 2D integer array highways where highways[i] = [city1i, city2i, tolli] indicates that there is a highway that connects city1i and city2i, allowing a car to go from city1i to city2i and vice versa for a cost of tolli.

You are also given an integer k. You are going on a trip that crosses exactly k highways. You may start at any city, but you may only visit each city at most once during your trip.

Return_ the maximum cost of your trip. If there is no trip that meets the requirements, return _-1_._

 

Example 1:

Input: n = 5, highways = [[0,1,4],[2,1,3],[1,4,11],[3,2,3],[3,4,2]], k = 3
Output: 17
Explanation:
One possible trip is to go from 0 -> 1 -> 4 -> 3. The cost of this trip is 4 + 11 + 2 = 17.
Another possible trip is to go from 4 -> 1 -> 2 -> 3. The cost of this trip is 11 + 3 + 3 = 17.
It can be proven that 17 is the maximum possible cost of any valid trip.

Note that the trip 4 -> 1 -> 0 -> 1 is not allowed because you visit the city 1 twice.

Example 2:

Input: n = 4, highways = [[0,1,3],[2,3,2]], k = 2
Output: -1
Explanation: There are no valid trips of length 2, so return -1.

 

Constraints:

• 2 <= n <= 15
• 1 <= highways.length <= 50
• highways[i].length == 3
• 0 <= city1i, city2i <= n - 1
• city1i != city2i
• 0 <= tolli <= 100
• 1 <= k <= 50
• There are no duplicate highways.

Solutions

Solution 1

class Solution:
  def maximumCost(self, n: int, highways: List[List[int]], k: int) -> int:
    if k >= n:
      return -1
    g = defaultdict(list)
    for a, b, cost in highways:
      g[a].append((b, cost))
      g[b].append((a, cost))
    f = [[-inf] * n for _ in range(1 << n)]
    for i in range(n):
      f[1 << i][i] = 0
    ans = -1
    for i in range(1 << n):
      for j in range(n):
        if i >> j & 1:
          for h, cost in g[j]:
            if i >> h & 1:
              f[i][j] = max(f[i][j], f[i ^ (1 << j)][h] + cost)
        if i.bit_count() == k + 1:
          ans = max(ans, f[i][j])
    return ans

class Solution {
  public int maximumCost(int n, int[][] highways, int k) {
    if (k >= n) {
      return -1;
    }
    List<int[]>[] g = new List[n];
    Arrays.setAll(g, h -> new ArrayList<>());
    for (int[] h : highways) {
      int a = h[0], b = h[1], cost = h[2];
      g[a].add(new int[] {b, cost});
      g[b].add(new int[] {a, cost});
    }
    int[][] f = new int[1 << n][n];
    for (int[] e : f) {
      Arrays.fill(e, -(1 << 30));
    }
    for (int i = 0; i < n; ++i) {
      f[1 << i][i] = 0;
    }
    int ans = -1;
    for (int i = 0; i < 1 << n; ++i) {
      for (int j = 0; j < n; ++j) {
        if ((i >> j & 1) == 1) {
          for (var e : g[j]) {
            int h = e[0], cost = e[1];
            if ((i >> h & 1) == 1) {
              f[i][j] = Math.max(f[i][j], f[i ^ (1 << j)][h] + cost);
            }
          }
        }
        if (Integer.bitCount(i) == k + 1) {
          ans = Math.max(ans, f[i][j]);
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int maximumCost(int n, vector<vector<int>>& highways, int k) {
    if (k >= n) {
      return -1;
    }
    vector<pair<int, int>> g[n];
    for (auto& h : highways) {
      int a = h[0], b = h[1], cost = h[2];
      g[a].emplace_back(b, cost);
      g[b].emplace_back(a, cost);
    }
    int f[1 << n][n];
    memset(f, -0x3f, sizeof(f));
    for (int i = 0; i < n; ++i) {
      f[1 << i][i] = 0;
    }
    int ans = -1;
    for (int i = 0; i < 1 << n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (i >> j & 1) {
          for (auto& [h, cost] : g[j]) {
            if (i >> h & 1) {
              f[i][j] = max(f[i][j], f[i ^ (1 << j)][h] + cost);
            }
          }
        }
        if (__builtin_popcount(i) == k + 1) {
          ans = max(ans, f[i][j]);
        }
      }
    }
    return ans;
  }
};

func maximumCost(n int, highways [][]int, k int) int {
  if k >= n {
    return -1
  }
  g := make([][][2]int, n)
  for _, h := range highways {
    a, b, cost := h[0], h[1], h[2]
    g[a] = append(g[a], [2]int{b, cost})
    g[b] = append(g[b], [2]int{a, cost})
  }
  f := make([][]int, 1<<n)
  for i := range f {
    f[i] = make([]int, n)
    for j := range f[i] {
      f[i][j] = -(1 << 30)
    }
  }
  for i := 0; i < n; i++ {
    f[1<<i][i] = 0
  }
  ans := -1
  for i := 0; i < 1<<n; i++ {
    for j := 0; j < n; j++ {
      if i>>j&1 == 1 {
        for _, e := range g[j] {
          h, cost := e[0], e[1]
          if i>>h&1 == 1 {
            f[i][j] = max(f[i][j], f[i^(1<<j)][h]+cost)
          }
        }
      }
      if bits.OnesCount(uint(i)) == k+1 {
        ans = max(ans, f[i][j])
      }
    }
  }
  return ans
}

function maximumCost(n: number, highways: number[][], k: number): number {
  if (k >= n) {
    return -1;
  }
  const g: [number, number][][] = Array.from({ length: n }, () => []);
  for (const [a, b, cost] of highways) {
    g[a].push([b, cost]);
    g[b].push([a, cost]);
  }
  const f: number[][] = Array(1 << n)
    .fill(0)
    .map(() => Array(n).fill(-(1 << 30)));
  for (let i = 0; i < n; ++i) {
    f[1 << i][i] = 0;
  }
  let ans = -1;
  for (let i = 0; i < 1 << n; ++i) {
    for (let j = 0; j < n; ++j) {
      if ((i >> j) & 1) {
        for (const [h, cost] of g[j]) {
          if ((i >> h) & 1) {
            f[i][j] = Math.max(f[i][j], f[i ^ (1 << j)][h] + cost);
          }
        }
      }
      if (bitCount(i) === k + 1) {
        ans = Math.max(ans, f[i][j]);
      }
    }
  }
  return ans;
}

function bitCount(i: number): number {
  i = i - ((i >>> 1) & 0x55555555);
  i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
  i = (i + (i >>> 4)) & 0x0f0f0f0f;
  i = i + (i >>> 8);
  i = i + (i >>> 16);
  return i & 0x3f;
}