Best Road Trip

• You are planning to drive from Richmond to L.A.
• You want to spend as little as possible on the gas and motels.
• So you need to pick the best route with cheapest motels and smallest cost of gas
• 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

Assignment 3

• Write a program cmsc401.java that reads the database of

The number of cities, N, in the first line. N>=3, N<=1000 The total number of direct highways between cities, M, in the second line. M>=2, M<=10000 Lowest motel price for each of N-2 cities (excluding L.A. and Richmond), each as a single line of two numbers: city number(3N), motel cost (1200) Gas prices for traveling direct highways between two cities, each as a single line of three numbers: city number (1N), city number (1N), cost of gas for travel between the two cities(1200) Richmond is city number 1, L.A. is city number 2 Cost shouldnt include a motel in Richmond, not in L.A.

573 784 875 981 4 985 4 451 5 1404 3 872 5 1503 5 1093 2 73

gas & motel costs, which is in the format below:

Example

Input in correct format Correct output

388

5

7

• 78
• 87
• 98

1 4 98

5 4 45

1 5 140

4 3 87

• 5 150
• 5 109 Green shows the cheapest route from city 1

3 2 73 (Richmond) to city 2 (L.A). Cost is $388:

$140+$150 for gas + $98 for motel

Remarks

• There will always be at least one way 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
• No other text, comments, questions on output

Constraints

• Any Java libraries, classes, functions related to graphs, vertices, edges are NOT allowed

Create your own

• Using Java queue or priority queue (and other simple data structures such as lists, hash maps) is allowed