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 (3…N), motel cost (1…200) – Gas prices for traveling direct highways between two cities, each as a single line of three numbers: city number (1…N), city number (1…N), cost of gas for travel between the two cities (1…200) – Richmond is city number 1, L.A. is city number 2 – Cost shouldn’t include a motel in Richmond, not in L.A. |
5
7 3 78 4 87 5 98 1 4 98 5 4 45 1 5 140 4 3 87 2 5 150 3 5 109 3 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
