Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <algorithm>
- #include <utility>
- #include <map>
- #include <list>
- #define debug_print false // pretty print things
- bool pp(std::list<std::string> &to_print) {
- std::cout << "[ ";
- for( auto it = to_print.begin(); it != to_print.end(); it++ ) {
- std::cout << "'" << *it << "' ";
- }
- std::cout << "]\n";
- return true;
- }
- int main(void)
- {
- int num_of_trips;
- std::map<std::string, std::list<std::string> > trips;
- // map with key -> list of strings
- std::cout << "Please, enter the number of trips you will provide: ";
- std::cin >> num_of_trips;
- // loop to insert all the entries
- for(int i = 0; i < num_of_trips; i++)
- {
- std::string city_a, city_b;
- std::cin >> city_a >> city_b;
- auto search_key = trips.find(city_a);
- if(search_key != trips.end()) {
- // found the key, insert on ordered position on the key
- search_key->second.insert(
- std::lower_bound(
- search_key->second.begin(),
- search_key->second.end(),
- city_b
- ),
- city_b
- );
- } else {
- // didn't found the key, insert a new entry on map
- trips.insert(
- std::pair<std::string, std::list<std::string> > (
- city_a,
- {city_b}
- )
- );
- }
- }
- std::list<std::string> itin;
- std::string actual_city;
- std::cout << "Please, enter the first city: ";
- std::cin >> actual_city;
- auto actual_it = trips.find(actual_city);
- // sanity check
- if( actual_it == trips.end() ) {
- std::cout << "City doesn't exist on the itinerary!\nExiting...\n";
- return 1;
- }
- std::string actual_city_name = actual_it->first;
- // populate itin with the actual itinerary
- while(true) {
- actual_it = trips.find(actual_city_name);
- if( actual_it != trips.end() ) {
- // exists
- itin.push_back(actual_it->first);
- if( actual_it->second.size() > 0 ) {
- actual_city_name = actual_it->second.front();
- actual_it->second.pop_front();
- } else {
- break;
- }
- } else {
- itin.push_back(actual_city_name);
- break;
- }
- }
- if( itin.size() != num_of_trips + 1 ){
- std::cout << "null" << std::endl;
- return 1;
- }
- pp(itin);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement