Description

Submission

class Solution {
    using ai3 = array<int, 3>; // distance, index, discounts left
public:
    int minimumCost(int n, vector<vector<int>>& highways, int discounts) {
        vector<unordered_map<int, int>> graph(n);

        for(auto& h: highways) {
            graph[h[0]][h[1]] = h[2];
            graph[h[1]][h[0]] = h[2];
        }

        priority_queue<ai3, vector<ai3>, greater<>> pq;
        vector<vector<int>> costs(n, vector<int>(discounts+1, INT_MAX));
        pq.push({0, 0, discounts});

        while(!pq.empty()) {
            auto [distance, cur, nDiscounts] = pq.top();
            pq.pop();

            if(costs[cur][nDiscounts] <= distance) continue;
            costs[cur][nDiscounts] = distance;

            if(cur == n - 1) return distance;

            for(auto [nxt, d]: graph[cur]) {
                // already updated, must be shorter than the current one
                if(costs[nxt][nDiscounts] != INT_MAX) continue;
                pq.push({d + distance, nxt, nDiscounts});
                if(nDiscounts >= 1) pq.push({d / 2 + distance, nxt, nDiscounts - 1});
            }
        }

        return -1;
    }
};