HardNo. 2247LeetCode Premium
Maximum Cost of Trip With K Highways — LeetCode 2247 Python Solution
- Pattern
- Bit Manipulation
- Topics
- Bit Manipulation, Graph, Dynamic Programming, Bitmask
- Reading time
- 4 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
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 ansComplexity
- Time
- O(2n × n2)
- Space · auxiliary
- O(2n × n)where n represents the number of cities
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2247. Maximum Cost of Trip With K Highways is filed here because LeetCode tags it Bit Manipulation and Bitmask, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0847 | Shortest Path Visiting All Nodes | Hard |
| 1494 | Parallel Courses II | Hard |
| 0464 | Can I Win | Medium |
| 0473 | Matchsticks to Square | Medium |
| 0526 | Beautiful Arrangement | Medium |
| 0638 | Shopping Offers | Medium |
Frequently asked questions
- How hard is LeetCode 2247. Maximum Cost of Trip With K Highways?
LeetCode 2247. Maximum Cost of Trip With K Highways is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2247. Maximum Cost of Trip With K Highways?
The Python solution on this page runs in O(2n × n2).
- What is the space complexity of LeetCode 2247. Maximum Cost of Trip With K Highways?
The Python solution on this page uses O(2n × n), where n represents the number of cities auxiliary space.
- What topics does LeetCode 2247. Maximum Cost of Trip With K Highways cover?
LeetCode 2247. Maximum Cost of Trip With K Highways is tagged Bit Manipulation, Graph, Dynamic Programming and Bitmask on LeetCode.
- Is LeetCode 2247. Maximum Cost of Trip With K Highways a premium problem?
Yes. LeetCode 2247. Maximum Cost of Trip With K Highways is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.