Second Best Road Trip You are planning to drive from Richmond to L.A. . You want to spend small amount on the gas and motels but also you do not want to go with the cheapest/best option to avoid other problems (e.g., low quality rooms, unexpected traffic congestion) Thus, you decided to pick the second best route. You have done your research and you know: - - cost of an overnight stay in the cheapest motel in each of the cities on the possible routes cost of driving between cities without overnight stays Now you need to write a program that will take all that data, and find the cheapest route - The route with lowest sum of motel and gas costs 10/30/22 VCU College of Engineering 2 Assignment 3 Write a program cmsc401.java that reads the database of gas & motel costs, which is in the format below: - - - - - The number of cities, N, in the first line. N>=3, N =2, M Example Input in correct format 5 7 Correct output 423 ($87) $98 1 11/1/22 3 78 4 87 5 98 14 98 5 4 45 1 5 140 4 3 87 2 5 150 3 5 109 32 73 $87 4 ($78) $45 $140 $73 $109 2 $150 ($98) Green shows the cheapest route from city 1 (Richmond) to city 2 (L.A) with cost $388: $140+$150 for gas + $98 for motel. Second cheapest route is shown in blue with cost $423: $98 + $87 + $73 for gas and $87 + $78 for motel. VCU College of Engineering 4 Remarks There will always be at least two ways of getting from city 1 to city 2 If a cost for gas from city A to B is in the input, cost for gas from B to A is the same and will not be in the input Complexity should be O(V). Any Java libraries, classes, functions related to graphs, vertices, edges are NOT allowed - Create your own (adjacency matrix or adjacency list) Using Java queue or priority queue (and other simple data structures such as lists, hash maps) is allowed No other text, comments, questions on output (you will lose points, if provided) 10/30/22 VCU College of Engineering 5 Remarks Hint: Consider finding the shortest path first, then try to use it to find the second shortest path by running the same algorithm (one of those covered in the class only) multiple times and with some adaptations to the graph. It is possible that second cheapest road might have the same cost with the best route. It is also possible that second cheapest route may have overlaps with the best route. 11/1/22 $50 $50 ($50) ($50) 3 $50 $50 $200 $50 ($50) VCU College of Engineering 6