Untitled
unknown
plain_text
4 months ago
2.6 kB
2
Indexable
#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 }
Editor is loading...
Leave a Comment