Using the concept of GRAPHS, you will write a program that will determine the shortest and fastest route from ONE LOCATION to a SPECIFIED location in METRO-MANILA. The program should have a database of the different cities and municipalities in Metro-Manila.

Your program should first identify possible locations where the USER will come from (source / start) and the DESTINATION (target location).

The program should ask the users from what CITY or MUNICIPALITY in METRO-MANILA will they START their travel. Once the CITY or MUNICIPALITY is identified, the program should ask the users WHERE, in the city or municipality identified, will they START. Your program should provide the different options WHERE theusers can START the travel.

In each of the cities or municipalities, you need to identify at least five (5) locations, you may want use more than five (5) just be sure that the locationsare scattered and far away from each other.The program should have the database of the possible ROUTE of the different locations and the time it takes to REACH one location to another location. This will serve as your MAP GRAPH of the locations with the corresponding travel time. Travel time should be in hours and minutes.Your program should then ask the users for the DESTINATION.

Your program should again ask for the CITY or MUNICIPALITY where the users would like to go. Once the city or municipality is identified, as WHERE in that city or municipality would the user would like to travel.

The program should be able to determine the shortest possible ROUTE and the TRAVEL TIME it will take the users to travel from the START (source) location to the DESTINATION (end).

C++ is the Language used in the Program. Thank you!