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: State Compression Dynamic Programming
We notice that the problem requires exactly $k$ roads to be passed, and each city can only be visited once. The number of cities is $n$, so we can pass at most $n - 1$ roads. Therefore, if $k \ge n$, we cannot meet the requirements of the problem, and we can directly return $-1$.
In addition, we can also find that the number of cities $n$ does not exceed $15$, which suggests that we can consider using the method of state compression dynamic programming to solve this problem. We use a binary number of length $n$ to represent the cities that have been passed, where the $i$-th bit is $1$ indicates that the $i$-th city has been passed, and $0$ indicates that the $i$-th city has not been passed yet.
We use $f[i][j]$ to represent the maximum travel cost when the cities that have been passed are $i$ and the last city passed is $j$. Initially, $f[2^i][i]=0$, and the rest $f[i][j]=-\infty$.
Consider how $f[i][j]$ transitions. For $f[i]$, we enumerate all cities $j$. If the $j$-th bit of $i$ is $1$, then we can reach city $j$ from other city $h$ through the road, at this time the value of $f[i][j]$ is the maximum value of $f[i][h]+cost(h, j)$, where $cost(h, j)$ represents the travel cost from city $h$ to city $j$. Therefore, we can get the state transition equation:
$$ f[i][j]=\max_{h \in \textit{city}}{f[i \backslash j][h]+cost(h, j)} $$
where $i \backslash j$ represents changing the $j$-th bit of $i$ to $0$.
After calculating $f[i][j]$, we judge whether the number of cities passed is $k+1$, that is, whether the number of $1$s in the binary representation of $i$ is $k+1$. If so, we update the answer as $ans = \max(ans, f[i][j])$.
The time complexity is $O(2^n \times n^2)$, and the space complexity is $O(2^n \times n)$, where $n$ represents the number of cities.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
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 |
|
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 |
|
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 |
|
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 |
|