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) {
        if (a.toll == b.toll) return a.discount < b.discount; // Ưu tiên vé nhiều hơn
        return a.toll > b.toll; // Ưu tiên chi phí thấp hơn
    }
};

int minCost[11][301];
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 < n; i++) {
        table[i].clear();
    }
    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; // Kiểm tra tồn tại
    int idx = mp[mId];
    road[idx].exist = false;
}

int cost(int M, int sCity, int eCity) {
    for (int i = 1; i <= 10; i++) {
        for (int j = 0; j < 301; j++) {
            minCost[i][j] = INT_MAX;
        }
    }
    priority_queue<Node, vector<Node>, cmp> pq;
    Node start;
    start.set(sCity, 0, M);
    pq.push(start);

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

        if (curNode == eCity) return curToll;
        if (curToll > minCost[curDis][curNode]) continue;

        for (auto idx : table[curNode]) {
            if (!road[idx].exist) continue;

            int nexNode = road[idx].en;
            int nexToll1 = road[idx].toll;
            int nexToll2 = road[idx].toll / 2;

            // Sử dụng vé
            if (curDis > 0) {
                if (curToll + nexToll2 < minCost[curDis - 1][nexNode]) {
                    Node temp;
                    temp.set(nexNode, curToll + nexToll2, curDis - 1);
                    pq.push(temp);
                    minCost[curDis - 1][nexNode] = curToll + nexToll2;
                }
            }
            // Không sử dụng vé
            if (curToll + nexToll1 < minCost[curDis][nexNode]) {
                Node temp;
                temp.set(nexNode, curToll + nexToll1, curDis);
                pq.push(temp);
                minCost[curDis][nexNode] = curToll + nexToll1;
            }
        }
    }
    return -1; // Không tìm thấy đường đi
}