Untitled
unknown
plain_text
6 months ago
2.9 kB
3
Indexable
#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; }
Editor is loading...
Leave a Comment