Find a Route (Id-1533)

Bonus Practice Sheet Winter 2018 [17-Mar-2018 to 7-Apr-2018]

Program ID- 1533

Rahul is fond of travelling and he visits cities and towns in the country whenever possible. All cities in the country are not connected to each other. Given the details of the cities that are connected to each city, source city from where he begins the travel and the destination city of the travel, design an algorithm and write a C++ code to list down the cities in the travel. Rahul must not visit a city more than once. When the destination city name is in the connected cities of the current city, chose it and complete the route. When the destination city name is not in the list of connected cities to current city and there are more than one city from the current city, he sorts the city names and include the first minimum city name that is not yet visited. For example, if the connection between the cities are given as follows, source city as A and destination city as F the list of cities in the travel are A, B, D and F.



City Connected Cities
A E, B
B D
C E,D
D F
E F


Use vectors, maps and algorithms such as sort, find in STL for implementation. Assume that the connection of cities is very simple and there is a path as described in the problem.

Input Format

Number of cities that are connected to other cities, ‘n’

Name of city1

Number of neighbouring cities for city1, ‘m’

First neighbouring city of city1

Second neighbouring city of city1

…

mth neighbouring city of city1

…

Name of cityn

Number of neighbouring cities for cityn, ‘m’

First neighbouring city of cityn

Second neighbouring city of cityn

…

mth neighbouring city of cityn



Output Format

Name of cities in the list


Please Comment Working if the code worked to you

If you have other working codes please comment the codes enclosing with <pre> and </pre> 

Example: <pre> Your Code </pre>

Code: C++

void travel::get()
{
cin>>num_Of_Cities;
for(int i=0;i<num_Of_Cities;i++)
 {int x;
 string temp1;
 cin>>temp1>>x;
 for(int j=0;j<x;j++)
 {string temp;
 cin>>temp;
 city_Connection[temp1].push_back(temp); 
 }
 }
cin>>source>>destn;
}
void travel::find_Route()
{
route.push_back(source);
while(route.back()!=destn)
{
 bool flag=true;
 vector<string> store=city_Connection[route.back()];
 sort(store.begin(),store.end());
 if(find(store.begin(),store.end(),destn)!=store.end())
 {route.push_back(destn);break;}
 for(int i=0;i<store.size();i++)
 if (find(route.begin(),route.end(),store[i])==route.end())
 {route.push_back(store[i]);flag=false;break;}
}
}
void travel::print_Route()
{
for(int i=0;i<route.size();i++)
 cout<<route[i]<<endl;
}

NOTE: The Above Codes are for reference only. It doesn't mean everyone to directly copy/paste those codes.