Description
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
• Write a program cmsc401.java that reads the database of
gas & motel costs, which is in the format below:
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
– 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.
Example
Input in correct format
11/17/16 4
Correct output
388
Green shows the cheapest route from city 1
(Richmond) to city 2 (L.A). Cost is $388:
$140+$150 for gas + $98 for motel
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
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
Submission
• Date due: Thursday, Dec 1st, 11:59 pm
• Upload through Blackboard
– Your submission should be a zip archive
4_FamilyName_FirstName.zip containing
• Java source code in a file cmsc401.java (all low case letters!)
– The file should have your name in a comment in the first line
– If you use multiple files, the main file must be cmsc401.java
– Remember: in Java, class name should match the file name, and
is case sensitive
• Please do NOT create your own packages
• Do NOT place the file into a folder – just zip the file
• Use standard I/O to read input (System.in, System.out) and output
• Make sure the program compiles
