Untitled

 avatar
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