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][11], numCity;
 
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;
        }
    }
}
 
//moi road co n trang thai: khong dung hoac dung n coupon (max n = 10)
//moi lan dung coupon thi so luong coupon trong road = so coupon da dung + 1
//mang gom 2 chieu: city di den + so coupon da su dung, value la tong toll de di den duong do
//cho het tat ca vao queue, duong nao nho hon thi dung duong do, neu dung duong co dung coupon thi tang so coupon da dung len, luu toll vao mang chua so coupon da dung
//ket qua la toll tai eCity
//khong thay duong ra thi return -1
 
int cost(int M, int sCity, int eCity) {
    priority_queue<road, vector<road>, cmp> pq;
    for(int i = 0; i < numCity; i++) {
        for(int j = 0; j < 11; j++) {
            toll[i][j] = 1000000;
            if(i == sCity) toll[i][j] = 0;
        }       
    }
    road start = {0, sCity, 0, 0, 0}; //sCity, eCity, id, coupon, toll;
    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]) {2
            int nextCity = i.eCity;
            int nextToll = curToll + i.toll;
            int nextTollDiscount = curToll + i.toll/2;
            if(nextToll < toll[nextCity][curCoupon]) {
                toll[nextCity][curCoupon] = nextToll;
                road a = {curCity, nextCity, i.id, curCoupon, nextToll};
                pq.push(a);
            }
            if(nextTollDiscount < toll[nextCity][curCoupon + 1] && curCoupon + 1 <= M) {
                toll[nextCity][curCoupon + 1] = nextTollDiscount;
                road a = {curCity, nextCity, i.id, curCoupon + 1, nextTollDiscount};
                pq.push(a);

            }
        }
    }
    return -1;
}