Untitled

 avatar
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