Untitled

const int MAXI = INT_MAX/2;
int dijkstra(vector<vector<pair<int, int>>>& adj, int n, int d) {
    vector<vector<int>> dis(n, vector<int>(d+1, MAXI));

    set<pair<int, pair<int, int>>> st;
    st.insert({0, {0, 0}});
    dis[0][0] = 0;

    while(!st.empty()) {
        pair<int, pair<int, int>> p = *(st.begin());
        int u = p.second.first, currCoupons = p.second.second;
        int currDis = p.first;

        for(pair<int, int> p : adj[u]) {
            int v = p.second, toll = p.first;

            // take coupon
            if(currCoupons + 1 <= d) {
                if(dis[v][currCoupons+1] > currDis + (toll/2)) {
                    st.erase({dis[v][currCoupons+1], {v, currCoupons+1}});
                    dis[v][currCoupons+1] = currDis + (toll/2);
                    st.insert({dis[v][currCoupons+1], {v, currCoupons+1}});
                }
            }

            // don't take coupon
            if(dis[v][currCoupons] > currDis + toll) {
                st.erase({dis[v][currCoupons], {v, currCoupons}});
                dis[v][currCoupons] = currDis + toll;
                st.insert({dis[v][currCoupons], {v, currCoupons}});
            }
        }
    }

    int ans = MAXI;
    for(int i=0; i<=d; i++) {
        ans = min(ans, dis[n-1][d]);
    }
    return ans;
}