Untitled

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

struct Road {
    int st;
    int en;
    int toll;
    bool exist;
    void set(int st, int en, int toll, bool exist) {
        this->st = st;
        this->en = en;
        this->toll = toll;
        this->exist = exist;
    }
} road[2001];

struct Node {
    int addr;
    int toll;
    int discount;
    void set(int addr, int toll, int discount) {
        this->addr = addr;
        this->toll = toll;
        this->discount = discount;
    }
};

struct cmp {
    bool operator()(Node a, Node b) {
        return a.toll > b.toll; // Ưu tiên chi phí thấp hơn
    }
};

unordered_map<int, int> mp;
int cnt = 0;
int n, k;
vector<int> table[301];

void init(int N, int K, int mId[], int sCity[], int eCity[], int mToll[]) {
    n = N;
    k = K;
    for (int i = 0; i < 301; i++) {
        table[i].clear();
    }
    cnt = 0; // Reset lại bộ đếm
    for (int i = 0; i < k; i++) {
        road[cnt].set(sCity[i], eCity[i], mToll[i], true);
        mp[mId[i]] = cnt;
        table[sCity[i]].push_back(cnt);
        cnt++;
    }
}

void add(int mId, int sCity, int eCity, int mToll) {
    road[cnt].set(sCity, eCity, mToll, true);
    mp[mId] = cnt;
    table[sCity].push_back(cnt);
    cnt++;
}

void remove(int mId) {
    if (mp.find(mId) == mp.end()) return; // Không tồn tại
    int idx = mp[mId];
    road[idx].exist = false;
}

int cost(int M, int sCity, int eCity) {
    priority_queue<Node, vector<Node>, cmp> pq;
    vector<int> visit(301, INT_MAX);
    
    Node start;
    start.set(sCity, 0, M);
    pq.push(start);

    while (!pq.empty()) {
        Node t = pq.top();
        pq.pop();
        int curCity = t.addr;
        int curToll = t.toll;
        int curM = t.discount;

        if (curCity == eCity) return curToll;

        for (auto it : table[curCity]) {
            if (road[it].exist) {
                int cost = road[it].toll;
                int nex = road[it].en;

                if (curM > 0 && curToll + cost / 2 < visit[nex]) {
                    Node tmp;
                    tmp.set(nex, curToll + cost / 2, curM - 1);
                    visit[nex] = curToll + cost / 2;
                    pq.push(tmp);
                }
                if (curToll + cost < visit[nex]) {
                    Node tmp;
                    tmp.set(nex, curToll + cost, curM);
                    visit[nex] = curToll + cost;
                    pq.push(tmp);
                }
            }
        }
    }
    return -1; // Không tìm thấy đường đi
}