Minimum Cost to Reach City With Discounts

class Solution {
public:
    int findMinCost(int totalCities, vector<vector<int>>& roads, int maxDiscounts) {
        // Building the graph using road information
        vector<vector<pair<int, int>>> adjacencyList(totalCities);
        for (auto &road : roads) {
            int city1 = road[0], city2 = road[1], cost = road[2];
            adjacencyList[city1].emplace_back(city2, cost);
            adjacencyList[city2].emplace_back(city1, cost);
        }

        // Priority queue to manage state exploration based on (totalCost, currentCity, discountsUsed)
        priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<>> minHeap;
        minHeap.emplace(0, 0, 0);  // Start from city 0 with no cost using 0 discounts

        // Table to store the minimum cost to reach each city using up to a certain number of discounts
        vector<vector<int>> costToReach(totalCities, vector<int>(maxDiscounts + 1, INT_MAX));
        costToReach[0][0] = 0;

        while (!minHeap.empty()) {
            auto [currentCost, currentCity, discountsUsed] = minHeap.top();
            minHeap.pop();

            // Ignore this state if it's not optimal
            if (currentCost > costToReach[currentCity][discountsUsed]) continue;

            // Check all possible moves from the current city
            for (auto &[nextCity, roadCost] : adjacencyList[currentCity]) {
                // Normal move without using a discount
                if (costToReach[nextCity][discountsUsed] > currentCost + roadCost) {
                    costToReach[nextCity][discountsUsed] = currentCost + roadCost;
                    minHeap.emplace(costToReach[nextCity][discountsUsed], nextCity, discountsUsed);
                }

                // Move using a discount if any remain
                if (discountsUsed < maxDiscounts) {
                    int reducedCost = currentCost + roadCost / 2;
                    if (costToReach[nextCity][discountsUsed + 1] > reducedCost) {
                        costToReach[nextCity][discountsUsed + 1] = reducedCost;
                        minHeap.emplace(reducedCost, nextCity, discountsUsed + 1);
                    }
                }
            }
        }

        // Determine the minimal cost to reach the last city with any discount level
        int leastCost = *min_element(costToReach[totalCities - 1].begin(), costToReach[totalCities - 1].end());
        return leastCost == INT_MAX ? -1 : leastCost;
    }
};

class Solution {

    public int findMinCost(int cities, int[][] roads, int maxDiscounts) {
        // Generate the map using the roads data
        List<List<int[]>> cityMap = new ArrayList<>();
        for (int i = 0; i < cities; ++i) {
            cityMap.add(new ArrayList<>());
        }
        for (int[] road : roads) {
            int from = road[0], to = road[1], cost = road[2];
            cityMap.get(from).add(new int[] { to, cost });
            cityMap.get(to).add(new int[] { from, cost });
        }

        // Priority queue to manage exploring paths
        PriorityQueue<int[]> pathQueue = new PriorityQueue<>(
            Comparator.comparingInt(a -> a[0])
        );
        pathQueue.offer(new int[] { 0, 0, 0 }); // Start at city 0 with no cost and no discounts used

        // Distance tracker for each city based on discount usage
        int[][] costs = new int[cities][maxDiscounts + 1];
        for (int[] costRow : costs) {
            Arrays.fill(costRow, Integer.MAX_VALUE);
        }
        costs[0][0] = 0;

        while (!pathQueue.isEmpty()) {
            int[] currentPath = pathQueue.poll();
            int cost = currentPath[0], currentCity = currentPath[1], usedDiscounts =
                currentPath[2];

            // Skip paths not optimal
            if (cost > costs[currentCity][usedDiscounts]) {
                continue;
            }

            // Traverse neighbors
            for (int[] neighbor : cityMap.get(currentCity)) {
                int adjacentCity = neighbor[0], pathCost = neighbor[1];

                // Explore without discount
                if (cost + pathCost < costs[adjacentCity][usedDiscounts]) {
                    costs[adjacentCity][usedDiscounts] = cost + pathCost;
                    pathQueue.offer(
                        new int[] {
                            costs[adjacentCity][usedDiscounts],
                            adjacentCity,
                            usedDiscounts,
                        }
                    );
                }

                // Explore using discount if available
                if (usedDiscounts < maxDiscounts) {
                    int discountedCost = cost + pathCost / 2;
                    if (
                        discountedCost < costs[adjacentCity][usedDiscounts + 1]
                    ) {
                        costs[adjacentCity][usedDiscounts + 1] = discountedCost;
                        pathQueue.offer(
                            new int[] {
                                discountedCost,
                                adjacentCity,
                                usedDiscounts + 1,
                            }
                        );
                    }
                }
            }
        }

        // Determine the minimal cost to reach the last city considering any discount count
        int lowestCost = Integer.MAX_VALUE;
        for (int d = 0; d <= maxDiscounts; ++d) {
            lowestCost = Math.min(lowestCost, costs[cities - 1][d]);
        }
        return lowestCost == Integer.MAX_VALUE ? -1 : lowestCost;
    }
}

class Solution:
    def findMinimumTravelCost(
        self, cities: int, roads: List[List[int]], discount_limit: int
    ) -> int:
        # Building the road map
        road_map = [[] for _ in range(cities)]
        for road in roads:
            start, end, cost = road
            road_map[start].append((end, cost))
            road_map[end].append((start, cost))

        # Priority queue to maintain state with (travel_cost, current_city, discounts_applied)
        pq = [(0, 0, 0)]  # Starting from city 0 at cost 0 using 0 discounts

        # Tracking minimum distances achievable per city based on discounts applied
        min_dist = [[float("inf")] * (discount_limit + 1) for _ in range(cities)]
        min_dist[0][0] = 0

        while pq:
            curr_cost, current_city, used_discounts = heapq.heappop(pq)

            # Ignore this state if we have found a better state earlier
            if curr_cost > min_dist[current_city][used_discounts]:
                continue

            # Check all possible movements from the current_city
            for adj_city, road_cost in road_map[current_city]:
                # Move to adjacent city without using an additional discount
                normal_cost = curr_cost + road_cost
                if normal_cost < min_dist[adj_city][used_discounts]:
                    min_dist[adj_city][used_discounts] = normal_cost
                    heapq.heappush(
                        pq,
                        (normal_cost, adj_city, used_discounts),
                    )

                # Move to adjacent city using a discount if possible
                if used_discounts < discount_limit:
                    discounted_cost = curr_cost + road_cost // 2
                    if discounted_cost < min_dist[adj_city][used_discounts + 1]:
                        min_dist[adj_city][used_discounts + 1] = discounted_cost
                        heapq.heappush(
                            pq,
                            (discounted_cost, adj_city, used_discounts + 1),
                        )

        # Determine the minimum cost to reach the last city using any number of discounts
        min_travel_cost = min(min_dist[cities - 1])
        return -1 if min_travel_cost == float("inf") else min_travel_cost