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(2^n \times n^2).

What is the space complexity of LeetCode 2247. Maximum Cost of Trip With K Highways?

The Python solution on this page uses O(2^n \times 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.

Maximum Cost of Trip With K Highways — LeetCode 2247 Python Solution

HardLeetCode PremiumBit ManipulationGraphDynamic ProgrammingBitmask

Problem: #2247
Pattern: Bit Manipulation
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

Python

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

Complexity

Measure	Complexity
Time	O(2^n \times n^2)
Space	O(2^n \times n), where n represents the number of cities auxiliary

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.

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(2^n \times n^2).
What is the space complexity of LeetCode 2247. Maximum Cost of Trip With K Highways?: The Python solution on this page uses O(2^n \times 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.