SHARE
TWEET

facebook-problem-c++

a guest Feb 22nd, 2019 92 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <utility>
  4. #include <map>
  5. #include <list>
  6.  
  7. #define debug_print false   // pretty print things
  8.  
  9. bool pp(std::list<std::string> &to_print) {
  10.     std::cout << "[ ";
  11.     for( auto it = to_print.begin(); it != to_print.end(); it++ ) {
  12.         std::cout << "'" << *it << "' ";
  13.     }
  14.     std::cout << "]\n";
  15.     return true;
  16. }
  17.  
  18. int main(void)
  19. {
  20.     int num_of_trips;
  21.     std::map<std::string, std::list<std::string> > trips;
  22.     // map with key -> list of strings
  23.  
  24.     std::cout << "Please, enter the number of trips you will provide: ";
  25.     std::cin >> num_of_trips;
  26.  
  27.     // loop to insert all the entries
  28.     for(int i = 0; i < num_of_trips; i++)
  29.     {
  30.         std::string city_a, city_b;
  31.         std::cin >> city_a >> city_b;
  32.  
  33.         auto search_key = trips.find(city_a);
  34.         if(search_key != trips.end()) {
  35.             // found the key, insert on ordered position on the key
  36.             search_key->second.insert(
  37.                     std::lower_bound(
  38.                         search_key->second.begin(),
  39.                         search_key->second.end(),
  40.                         city_b
  41.                         ),
  42.                     city_b
  43.                     );
  44.         } else {
  45.             // didn't found the key, insert a new entry on map
  46.             trips.insert(
  47.                     std::pair<std::string, std::list<std::string> > (
  48.                         city_a,
  49.                         {city_b}
  50.                         )
  51.                     );
  52.         }
  53.     }
  54.    
  55.     std::list<std::string> itin;
  56.     std::string actual_city;
  57.  
  58.     std::cout << "Please, enter the first city: ";
  59.     std::cin >> actual_city;
  60.  
  61.     auto actual_it = trips.find(actual_city);
  62.  
  63.     // sanity check
  64.     if( actual_it == trips.end() ) {
  65.         std::cout << "City doesn't exist on the itinerary!\nExiting...\n";
  66.         return 1;
  67.     }
  68.  
  69.     std::string actual_city_name = actual_it->first;
  70.  
  71.     // populate itin with the actual itinerary
  72.     while(true) {
  73.         actual_it = trips.find(actual_city_name);
  74.         if( actual_it != trips.end() ) {
  75.             // exists
  76.             itin.push_back(actual_it->first);
  77.             if( actual_it->second.size() > 0 ) {
  78.                 actual_city_name = actual_it->second.front();
  79.                 actual_it->second.pop_front();
  80.             } else {
  81.                 break;
  82.             }
  83.         } else {
  84.             itin.push_back(actual_city_name);
  85.             break;
  86.         }
  87.     }
  88.  
  89.     if( itin.size() != num_of_trips + 1 ){
  90.         std::cout << "null" << std::endl;
  91.         return 1;
  92.     }
  93.  
  94.     pp(itin);
  95.     return 0;
  96. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top