Untitled
unknown
c_cpp
a year ago
2.8 kB
5
Indexable
#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); } } } } }
Editor is loading...
Leave a Comment