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 <= 151 <= highways.length <= 50highways[i].length == 30 <= city1i, city2i <= n - 1city1i != city2i0 <= tolli <= 1001 <= k <= 50- There are no duplicate highways.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| 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
|
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
| 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;
}
}
|
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
| 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;
}
};
|
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
| 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
}
|
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
| 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;
}
|
