The problem is that air fares are not necessarily proportional to the distance flown or to the number of stops. The cost of a flight may depend more upon the amount of competition than any other factor. In order to find the best route, it is necessary to check many possible alternatives. You are to write a program that selects the least expensive route for an airplane trip. Input to the program will be a list of all available flights between pairs of cities, along with the cost of each.
Output is to be the total cost and a description of the chosen route.
ToCity Cost FromCity ToCity Cost FromCity ToCity Cost . Cities are numbered from 1 to NumberOfCities, and NumberOfCities will not exceed 6. Only the listed flights are available. Your program is to print out the least expensive route from StartCity to EndCity as well as the total cost. You may assume that a path exists from the start city to the end city.