Untitled
unknown
plain_text
4 months ago
3.5 kB
4
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; 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 }
Editor is loading...
Leave a Comment