Skip to content

Latest commit

 

History

History
214 lines (169 loc) · 7.29 KB

_2093. Minimum Cost to Reach City With Discounts.md

File metadata and controls

214 lines (169 loc) · 7.29 KB

2093. Minimum Cost to Reach City With Discounts

All prompts are owned by LeetCode. To view the prompt, click the title link above.

Back to top

First completed : July 23, 2024

Last updated : July 23, 2024

Related Topics : Graph, Heap (Priority Queue), Shortest Path

Acceptance Rate : 59.8 %

Notes

Discount total = total cost - (top DISCOUNT costs / 2)

Version 1

First attempt was extremly inefficient due to the constant parsing of next nodes and the potential for $n*discounts$ number of heap values. I think a large part was actually due to my attempt to make it more efficient by checking the existing cases if there are less discounts remaining lol.

Took upwards of 7000ms but did in fact pass the test cases.

Version 2

Changed to a $n\times n$ matrix to parse data instead which proved much more efficient sitting around 1700ms compared to the previous.

Version 3

Updated it since we're performing a Dijstra's algo based on a heap, the first time we reach the node will with certainty be the shortest path.

This brougth it down further to just around 420ms.

Version 4

Swapped out the $n\times n$ matrix for a list of $n$ dicts but it didn't have any notable benefitial difference compared to version 3. However, depending on the number of discounts (if much greater) and a much larger network of cities, this may be better in that larger scale.

With the current test cases, it hovers at around 480ms.

Solutions

Python

m2093 v1 Weekly Premium.py

class Solution:
    def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
        hp = [(0, discounts, 0)]   # schema: (cumu cost, discounts, city)

        path = [[] for _ in range(n)]
        for c1, c2, toll in highways :
            path[c1].append((c2, toll))
            path[c2].append((c1, toll))

        visited = [[] for _ in range(n)] # schema: [(cost, discounts)]
        targetCost = -1

        while hp :
            cost, discLeft, city = heapq.heappop(hp)

            # End city reached so go no further
            if city == n - 1 :
                if targetCost == -1 or targetCost > cost :
                    targetCost = cost
                continue

            # Check if "favourable" case
            cont = False
            if visited[city] :
                for c, d in visited[city] :
                    if d >= discLeft and cost >= c :
                        cont = True
                        break

            if cont :
                continue
            visited[city].append((cost, discLeft))

            for nextCity, toll in path[city] :
                heapq.heappush(hp, (cost + toll, discLeft, nextCity))
                if discLeft :
                    heapq.heappush(hp, (cost + (toll // 2), discLeft - 1, nextCity))

        return targetCost

m2093 v2 nxn dijkstras.py

class Solution:
    def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
        hp = [(0, discounts, 0)]   # schema: (cumu cost, discounts, city)

        path = [[] for _ in range(n)]
        for c1, c2, toll in highways :
            path[c1].append((c2, toll))
            path[c2].append((c1, toll))

        cityCosts = [[inf] * (discounts + 1) for _ in range(n)]
        cityCosts[0][0] = 0

        while hp :
            cost, discRem, city = heapq.heappop(hp)

            if cost > cityCosts[city][discRem] :
                continue

            for nxtCity, toll in path[city] :
                if cost + toll < cityCosts[nxtCity][discRem] :
                    cityCosts[nxtCity][discRem] = cost + toll
                    heapq.heappush(hp, (cost + toll, discRem, nxtCity))
                if discRem and cost + toll // 2 < cityCosts[nxtCity][discRem - 1] :
                    cityCosts[nxtCity][discRem - 1] = cost + toll // 2
                    heapq.heappush(hp, (cost + toll // 2, discRem - 1, nxtCity))
        
        minCost = min(cityCosts[-1])
        return minCost if minCost != inf else -1

m2093 v3 nxn dijkstras with a proper break.py

''' Notes
    Discount total = total cost - (top DISCOUNT costs / 2)
'''

class Solution:
    def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
        hp = [(0, discounts, 0)]   # schema: (cumu cost, discounts, city)

        path = [[] for _ in range(n)]
        for c1, c2, toll in highways :
            path[c1].append((c2, toll))
            path[c2].append((c1, toll))

        cityCosts = [[inf] * (discounts + 1) for _ in range(n)]
        cityCosts[0][0] = 0

        while hp :
            cost, discRem, city = heapq.heappop(hp)

            if city == n - 1 :
                return cost

            if cost > cityCosts[city][discRem] :
                continue

            for nxtCity, toll in path[city] :
                if cost + toll < cityCosts[nxtCity][discRem] :
                    cityCosts[nxtCity][discRem] = cost + toll
                    heapq.heappush(hp, (cost + toll, discRem, nxtCity))
                if discRem and cost + toll // 2 < cityCosts[nxtCity][discRem - 1] :
                    cityCosts[nxtCity][discRem - 1] = cost + toll // 2
                    heapq.heappush(hp, (cost + toll // 2, discRem - 1, nxtCity))

        return -1

m2093 v4 list of dicts.py

''' Notes
    Discount total = total cost - (top DISCOUNT costs / 2)
'''

class Solution:
    def minimumCost(self, n: int, highways: List[List[int]], discounts: int) -> int:
        hp = [(0, discounts, 0)]   # schema: (cumu cost, discounts, city)

        path = [[] for _ in range(n)]
        for c1, c2, toll in highways :
            path[c1].append((c2, toll))
            path[c2].append((c1, toll))

        cityCosts = [{} for _ in range(n)]
        cityCosts[0][0] = 0

        while hp :
            cost, discRem, city = heapq.heappop(hp)

            if city == n - 1 :
                return cost

            if cost > cityCosts[city].get(discRem, inf) :
                continue

            for nxtCity, toll in path[city] :
                if cost + toll < cityCosts[nxtCity].get(discRem, inf) :
                    cityCosts[nxtCity][discRem] = cost + toll
                    heapq.heappush(hp, (cost + toll, discRem, nxtCity))
                if discRem and cost + toll // 2 < cityCosts[nxtCity].get(discRem - 1, inf) :
                    cityCosts[nxtCity][discRem - 1] = cost + toll // 2
                    heapq.heappush(hp, (cost + toll // 2, discRem - 1, nxtCity))

        return -1