_2473. Minimum Cost to Buy Apples.md

2473. Minimum Cost to Buy Apples

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

Back to top

---

First completed : June 29, 2024

Last updated : June 29, 2024

---

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

Acceptance Rate : 67.5 %

---

Solutions

• m2473.py

Python

m2473.py

class Solution:
    def minCost(self, n: int, roads: List[List[int]], appleCost: List[int], k: int) -> List[int]:
        travelCostMultiplier = k + 1
        output = []

        roadChoices = defaultdict(list)

        for road in roads :
            roadChoices[road[0]].append((road[1], road[2]))
            roadChoices[road[1]].append((road[0], road[2]))

        for i in range(1, n + 1) :
            toVisit = []            # (totalRoadCost, targetIndx)
            toVisit.append((0, i))
            distances = [inf] * n

            while toVisit :
                cost, node = heapq.heappop(toVisit)
                if distances[node - 1] != inf :
                    continue

                distances[node - 1] = cost

                for nextNode, additionalCost in roadChoices[node] :
                    heapq.heappush(toVisit, (cost + additionalCost, nextNode))
            
            output.append(min([distances[x] * travelCostMultiplier + appleCost[x] for x in range(n)]))
        
        return output