2093. Minimum Cost to Reach City With Discounts

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.

You are also given an integer discounts which represents the number of discounts you have. You can use a discount to travel across the ith highway for a cost of tolli / 2 (integer division). Each discount may only be used once, and you can only use at most one discount per highway.

Return the minimum total cost to go from city 0 to city n - 1, or -1 if it is not possible to go from city 0 to city n - 1.

class Solution {
public:
    int minimumCost(int n, vector<vector<int>>& highways, int discounts) {
        vector<vector<int>> vis(n, vector<int>(discounts + 1, INT_MAX));
        vis[0][discounts] = 0;
        vector<vector<pair<int, int>>> adj(n);
        for(auto& h : highways) {
            int u = h[0], v = h[1], c = h[2];
            adj[u].push_back({v,c});
            adj[v].push_back({u,c});
        }
        priority_queue<array<int, 3>, vector<array<int, 3>>, greater<array<int, 3>>> q;
        q.push({0,discounts,0});
        while(!q.empty()) {
            auto [cost, dis, u] = q.top(); q.pop();
            if(vis[u][dis] != cost) continue;
            
            for(auto [v, c] : adj[u]) {
                if(vis[v][dis] > cost + c) {
                    vis[v][dis] = cost + c;
                    q.push({cost + c, dis, v});
                }
                if(dis and vis[v][dis-1] > cost + c / 2) {
                    vis[v][dis-1] = cost + c / 2;
                    q.push({cost + c / 2, dis - 1, v});
                }
            }
        }
        int res = *min_element(begin(vis[n-1]), end(vis[n-1]));
        return res == INT_MAX ? -1 : res;
    }
};