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;
    long long toll;  // Thay đổi sang long long để tránh tràn số
    int discount;
    void set(int addr, long long toll, int discount) {
        this->addr = addr;
        this->toll = toll;
        this->discount = discount;
    }
};

struct cmp {
    bool operator()(const Node& a, const Node& b) {
        if (a.toll == b.toll) return a.discount < b.discount;
        return a.toll > b.toll;
    }
};

long long minCost[11][301];  // Thay đổi sang long long
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;
    cnt = 0;  // Đặt lại cnt
    mp.clear();  // Xóa map
    for (int i = 0; i < 301; 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;
    int idx = mp[mId];
    road[idx].exist = false;
}

int cost(int M, int sCity, int eCity) {
    // Đặt lại mảng minCost với giá trị rất lớn
    for (int i = 0; i <= 10; i++) {
        for (int j = 0; j < 301; j++) {
            minCost[i][j] = LLONG_MAX;
        }
    }
    
    priority_queue<Node, vector<Node>, cmp> pq;
    Node start;
    start.set(sCity, 0, M);
    pq.push(start);
    minCost[M][sCity] = 0;  // Đảm bảo chi phí ban đầu được đặt

    while (!pq.empty()) {
        Node t = pq.top();
        pq.pop();
        
        int curNode = t.addr;
        long long curToll = t.toll;
        int curDis = t.discount;
        
        if (curNode == eCity) return curToll;
        
        // Chỉ tiếp tục nếu chi phí hiện tại tốt hơn hoặc bằng chi phí đã ghi nhận
        if (curToll > minCost[curDis][curNode]) continue;
        
        for (auto idx : table[curNode]) {
            if (!road[idx].exist) continue;
            
            int nexNode = road[idx].en;
            long long nexToll1 = road[idx].toll;
            long long nexToll2 = road[idx].toll / 2;
            
            // Sử dụng vé
            if (curDis > 0) {
                long long newToll = curToll + nexToll2;
                if (newToll < minCost[curDis - 1][nexNode]) {
                    Node temp;
                    temp.set(nexNode, newToll, curDis - 1);
                    pq.push(temp);
                    minCost[curDis - 1][nexNode] = newToll;
                }
            }
            
            // Không sử dụng vé
            long long newToll = curToll + nexToll1;
            if (newToll < minCost[curDis][nexNode]) {
                Node temp;
                temp.set(nexNode, newToll, curDis);
                pq.push(temp);
                minCost[curDis][nexNode] = newToll;
            }
        }
    }
    
    return -1; // Không tìm thấy đường đi
}