Untitled
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