Untitled

#include <queue>
#include <vector>
#include <unordered_map>
using namespace std;

struct road {
    int sCity, eCity, id, coupon, toll;
} roads[3500];
int roadIdx;

class cmp {
public:
    bool operator() (road a, road b) {
        return a.toll > b.toll;
    }
};

vector<road> map[303]; 
unordered_map<int, int> hashRoad; //id + idx
int toll[303][2], numCity; // Chỉ cần 2 cột: 0 là không dùng coupon, 1 là dùng coupon

void add(int mId, int sCity, int eCity, int mToll) {
    hashRoad[mId] = roadIdx;
    roads[roadIdx].sCity = sCity;
    roads[roadIdx].eCity = eCity;
    roads[roadIdx].id = mId;
    roads[roadIdx].toll = mToll;
    roads[roadIdx].coupon = 0;
    map[sCity].push_back(roads[roadIdx]);
    roadIdx++;
}

void init(int N, int K, int mId[], int sCity[], int eCity[], int mToll[]) {
    roadIdx = 0;
    numCity = N;
    hashRoad.clear();
    for(int i = 0; i < N; i++) {
        map[i].clear();
    }
    for(int i = 0; i < K; i++) {
        add(mId[i], sCity[i], eCity[i], mToll[i]);
    }
}

void remove(int mId) {
    int idx = hashRoad[mId];
    hashRoad.erase(mId);
    int sCity = roads[idx].sCity;
    for(int i = 0; i < map[sCity].size(); i++) {
        if(map[sCity][i].id == mId) {
            map[sCity].erase(map[sCity].begin() + i);
            break;
        }
    }
}

int cost(int M, int sCity, int eCity) {
    priority_queue<road, vector<road>, cmp> pq;
    for(int i = 0; i < numCity; i++) {
        toll[i][0] = toll[i][1] = 1000000; // Khởi tạo cả hai cột
        if(i == sCity) {
            toll[i][0] = 0; // Không dùng coupon ở điểm bắt đầu
            toll[i][1] = 0; // Dùng coupon ở điểm bắt đầu (nếu có)
        }
    }
    road start = {0, sCity, 0, 0, 0}; // Khởi tạo đường đi từ sCity
    pq.push(start);

    while(!pq.empty()) {
        road top = pq.top();
        int curId = top.id;
        int curCity = top.eCity;
        int curToll = top.toll;
        int curCoupon = top.coupon;
        pq.pop();

        if(curCity == eCity) return curToll;

        for(auto i : map[curCity]) {
            int nextCity = i.eCity;
            int nextToll = curToll + i.toll;
            int nextTollDiscount = curToll + i.toll / 2;

            // Trường hợp không dùng coupon (toll[303][0])
            if(nextToll < toll[nextCity][curCoupon]) {
                toll[nextCity][curCoupon] = nextToll;
                road a = {curCity, nextCity, i.id, curCoupon, nextToll};
                pq.push(a);
            }

            // Trường hợp dùng coupon (toll[303][1])
            if(curCoupon == 0 && nextTollDiscount < toll[nextCity][1] && M >= 1) {
                toll[nextCity][1] = nextTollDiscount;
                road a = {curCity, nextCity, i.id, 1, nextTollDiscount};
                pq.push(a);
            }
        }
    }
    return -1;
}