You are planning a 6 city business trip to your satellite offices. You are located in Boston. You are afraid to fly, so you have decided driving is your best option. Gas is about$2.45/gal, and your car gets on average of 30 MPG. Determine using NEAREST NEIGHBOR starting and stopping fromBOSTON what your route will be, how many gallons of gas you will use, and estmated gas cost for the journey. Extra Credit (20 points): Find a cheaper route. Explain what method you used to find it.

Boston Cincinnat Cleveland Detroit New York Philadelphia Boston * 840 628 734 222 296 Cincinnat 840 * 244 269 647 567 Cleveland 628 244 * 170 473 413 Detroit 734 269 170 * 641 573 New York 222 647 473 641 * 101 Philadelphia 296 567 413 573 101