Untitled
unknown
plain_text
5 months ago
2.1 kB
4
Indexable
#include <queue> #include <vector> #include <unordered_map> #include <cstring> 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; } }node; struct cmp{ bool operator() (Node a, Node b) { return a.toll < b.toll; } }; 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; memset(table, 0, 301); 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) { int idx = mp[mId]; road[idx].exist = false; } int cost(int M, int sCity, int eCity) { priority_queue<Node, vector<Node>, cmp> pq; int visit[301]; for(int i=0; i<n; i++) { visit[i] = INT_MAX; } node.set(sCity, 0, M); pq.push(node); 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 == true) { 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]) { visit[nex] = curToll + cost; Node tmp; tmp.set(nex, curToll + cost, curM); pq.push(tmp); } } } } return -1; }
Editor is loading...
Leave a Comment