Untitled

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

vector< pair<int, int> > fw[250][250]; // cost, airline
int c, n;

void addFlight(int c1, int c2, int cost, int airline) {
    for(auto flight = fw[c1][c2].begin(); flight < fw[c1][c2].end(); flight++) {
        if(flight->second == airline) {
            flight->first = cost;
            return;
        }
    }
    fw[c1][c2].push_back(make_pair(cost, airline));
}

int minCost(int c1, int c2) {
    int vis[250];
    for(int i = 0; i < c; i++)
        vis[i] = 0;
    vis[c1] = 1;
    pair<int, int> price[250];
    pair<int, int> minCity;
    price[c1] = make_pair(0, -1);

    for(int i = 0; i < c; i++) { // initialize the starting node
        minCity = make_pair(MAX, -1);
        if(!fw[c1][i].empty()) {
            for(auto flight: fw[c1][i]) {
                minCity = minCity.first > flight.first ? flight : minCity;
            }
        }
        if(i != c1)
            price[i] = minCity;
    }

    for(int i = 0; i < c; i++) {

        int u = -1;
        for(int city = 0; city < c; city++) { // Choose the min node from the starting node
            if(vis[city] == 0 && u == -1)
                u = city;
            if(vis[city] == 0 && price[u].first > price[city].first)
                u = city;
        }

        if(u != -1)
            vis[u] = 1;
        else 
            break;
        
        for(int j = 0; j < c; j++) { // search all the node
            if(fw[u][j].size() != 0 && vis[j] == 0) {
                for(auto flight: fw[u][j]) {
                    int change = 0;
                    if(flight.second != price[u].second && price[u].second != -1)
                        change = 5;
                    if(price[j].first > ( flight.first + price[u].first + change )) {
                        price[j] = make_pair(( flight.first + price[u].first + change ), flight.second);
                    }
                }
            }
        }
    }

    return price[c2].first;
}

int main() {
    string move;
    cin >> c >> n;
    for(int i = 0;  i < n; i++) {
        cin >> move;
        int c1, c2, money, airline;
        if(move == "Add") {
            cin >> c1 >> c2 >> money >> airline;
            addFlight(c1, c2, money, airline);
        }
        else if(move == "Request") {
            cin >> c1 >> c2 >> money;
            int cost = minCost(c1, c2);
            if(cost > money) 
                cout << "-1\n";
            else
                cout << cost << endl;
            // cout << cost << endl;
        }
        else { // Delete
            cin >> c1 >> c2 >> airline;
            for(auto a = fw[c1][c2].begin(); a < fw[c1][c2].end(); a++) {
                if(a->second == airline) {
                    fw[c1][c2].erase(a);
                }
            }
        }
    }
}
Leave a Comment