Untitled

mail@pastecode.io avatar
unknown
c_cpp
23 days ago
1.7 kB
1
Indexable
Never
#include <iostream>
#include <vector>
#define MAX 20000
using namespace std;

struct flight {
    int money;
    int city;
    int airline;
};

vector<flight> node[250]; 
int cost = MAX;
int c, n;

void minCost(int c1, int c2, int cur_cost, int pre_air, int pre_city) {
    if(c1 == c2) {
        cost = min(cost, cur_cost);
        return;
    }
    for(auto f: node[c1]) {
        if(pre_city == f.city)
            continue;
        if(pre_air == f.airline || pre_air == -1) {
            minCost(f.city, c2, cur_cost + f.money, f.airline, c1);
        }
        else{
            minCost(f.city, c2, cur_cost + f.money + 5, f.airline, c1);
        }
    }
}

int main() {
    string move;
    cin >> c >> n;
    for(int i = 0;  i < n; i++) {
        cin >> move;
        int c1, c2, money, airline;
        // cout << "move = " << move << endl;
        if(move == "Add") {
            cin >> c1 >> c2 >> money >> airline;
            flight f;
            f.city = c2, f.money = money, f.airline = airline;
            node[c1].push_back(f);
        }
        else if(move == "Request") {
            cin >> c1 >> c2 >> money;
            cost = MAX;
            minCost(c1, c2, 0, -1, -1);
            if(cost > money) 
                cout << "-1" << endl;
            else
                cout << cost << endl;
            // cout << cost << endl;
        }
        else { // Delete
            cin >> c1 >> c2 >> airline;
            for(auto f = node[c1].begin(); f < node[c1].end(); f++) {
                if(f->airline == airline && f->city == c2) {
                    node[c1].erase(f);
                    break;
                }
            }
        }
    }
}
Leave a Comment