Untitled
unknown
plain_text
6 months ago
3.4 kB
3
Indexable
#include<iostream> #include<utility> #include<limits.h> #include<queue> #include<vector> #define MAXN 101 using namespace std; vector<pair<int, int>> graph[MAXN]; int cycle[MAXN]; int cost[MAXN][3]; int ttime[MAXN][3]; int walk = 0; int cyc = 1; int taxi = 2; struct dest { int city; int mode; int time; int cost; }; struct comp { bool operator()(dest a, dest b)const { if (a.cost == b.cost) { return a.time > b.time; } else { return a.cost > b.cost; } } }; void init(int N) { for (int i = 0; i < MAXN; i++) { graph[i].clear(); cycle[i] = 0; } } void addRoad(int K, int mSpotA[], int mSpotB[], int mDis[]) { for (int i = 0; i < K; i++) { graph[mSpotA[i]].push_back({ mSpotB[i],mDis[i] }); graph[mSpotB[i]].push_back({ mSpotA[i],mDis[i] }); } } void addBikeRent(int mSpot) { cycle[mSpot] = 1; } int getMinMoney(int mStartSpot, int mEndSpot, int mMaxTime) { for (int i = 0; i < MAXN; i++) { for (int j = 0; j < 3; j++) { cost[i][j] = INT_MAX; ttime[i][j] = INT_MAX; } } for (int i = 0; i < 3; i++) { cost[mStartSpot][i] = 0; ttime[mStartSpot][i] = 0; } priority_queue<dest, vector<dest>, comp> pq; pq.push({ mStartSpot,taxi, 7 ,0 }); while (!pq.empty()) { dest curNode= pq.top(); pq.pop(); if (curNode.time > mMaxTime) continue; if (curNode.cost > cost[curNode.city][curNode.mode] && curNode.time > ttime[curNode.city][curNode.mode]) continue; if (curNode.city == mEndSpot) { if (curNode.mode != cyc || cycle[curNode.city] == 1) { return curNode.cost; } } cost[curNode.city][curNode.mode] = min(curNode.cost, cost[curNode.city][curNode.mode]); ttime[curNode.city][curNode.mode] = min(curNode.time, ttime[curNode.city][curNode.mode]); for (auto neighbour : graph[curNode.city]) { int v = neighbour.first; int d = neighbour.second; if (curNode.mode == walk) { pq.push({ v, walk, curNode.time + d * 17, curNode.cost }); pq.push({ v, taxi, curNode.time + d * 1 + 7, curNode.cost + d * 19 }); if (cycle[curNode.city] == 1) pq.push({ v, cyc, curNode.time + d * 4, curNode.cost + d * 4 }); } else if (curNode.mode == cyc) { if (cycle[curNode.city] == 0) { pq.push({ v, cyc, curNode.time + d * 4, curNode.cost + d * 4 }); } else { pq.push({ v, walk, curNode.time + d * 17, curNode.cost }); pq.push({ v, taxi, curNode.time + d * 1 + 7, curNode.cost + d * 19 }); pq.push({ v, cyc, curNode.time + d * 4, curNode.cost + d * 4 }); } } else { pq.push({ v, walk, curNode.time + d * 17, curNode.cost }); pq.push({ v, taxi, curNode.time + d * 1, curNode.cost + d * 19 }); if (cycle[curNode.city] == 1) pq.push({ v, cyc, curNode.time + d * 4, curNode.cost + d * 4 }); } } } return -1; }
Editor is loading...
Leave a Comment