Trip Planning
In planning a trip by automobile, several routes might be considered. Some roads may be direct, but speed limits vary according to the type of road. Further, travel through cities may take longer than routes that avoid driving through city centers. This problem considers finding routes in Iowa that will take the least amount of time from one city to another. For reference, the Iowa Department of Transportation posts a map of the main routes in Iowa. Most highways run north-south or east-west; interstate highways run through the middle of the state, US highways and some state roads run in some areas with reasonably high speed, and rural or county roads connect many smaller towns.
In this problem, we consider the main interstates, US highways, state roads, and county roads. We do not consider small connecting roads, improved gravel roads, or rough gravel streets intended for low-speed farm travel. Further, all routes start at a designated starting city, go from one city to an adjacent city, until a destination city is reached.
The following table identifies the time (in mimutes) for direct travel from one city to another within the northeastern quadrant of Iowa. (Data from Google maps, accessed January 2, 2015.) A dash indicates there is not a direct highway between cities, so a traveler must follow a path through intermediate cities on the way.
| Ames | Cedar Rapids | Charles City | Clinton | Davenport | Decorah | Des Moines | Dubuque | Grinnell | Iowa City | Iowa Falls | Manchester | Maquoketa | Marshalltown | Mason City | Nevada | New Hampton | Waterloo | Webster City | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Ames | — | 35 min. | 50 min. | 14 min | 44 min | ||||||||||||||
| Cedar Rapids | — | 98 min. | 141 min. | 77 min. | 74 min. | 32 min. | 54 min. | 70 min. | 76 min. | 51 min. | |||||||||
| Charles City | — | 78 min. | 39 min. | 22 min. | 48 min. | ||||||||||||||
| Clinton | 98 min. | — | 47 min. | 43 min. | |||||||||||||||
| Davenport | 47 min. | — | 74 min. | 59 min. | 44 min. | ||||||||||||||
| Decorah | 141 min. | — | 115 min. | 90 min. | 48 min. | ||||||||||||||
| Des Moines | 35 min | — | 51 min. | 54 min. | |||||||||||||||
| Dubuque | 77 min. | 74 min. | 115 min. | — | 89 min. | 47 min. | 33 min. | 87 min. | |||||||||||
| Grinnell | 74 min. | 51 min. | — | 63 min. | 92 min. | 38 min. | 80 min. | ||||||||||||
| Iowa City | 32 min. | 59 min. | 89 min. | 63 min. | — | 77 min. | |||||||||||||
| Iowa Falls | 50 min. | 78 min. | 92 min. | — | 57 min. | 58 min. | 51 min. | 54 min. | 35 min. | ||||||||||
| Manchester | 54 min. | 44 min. | 90 min. | 47 min. | 77 min. | — | 68 min. | 48 min. | |||||||||||
| Maquoketa | 70 min. | 43 min | 33 min. | 68 min. | — | ||||||||||||||
| Marshalltown | 76 min. | 54 min. | 38 min. | 57 min. | — | 36 min. | 64 min. | ||||||||||||
| Mason City | 39 min. | 58 min. | — | 91 min. | 70 min. | ||||||||||||||
| Nevada | 14 min. | 51 min. | 36 min. | 91 min. | — | 78 min. | |||||||||||||
| New Hampton | 22 min. | 48 min. | — | 44 min. | |||||||||||||||
| Waterloo | 51 min. | 48 min. | 87 min. | 80 min. | 54 min. | 48 min. | 64 min. | 44 min. | — | ||||||||||
| Webster City | 44 min. | 35 min. | 70 min. | 78 min. | — |
Write a program that reads two cities and determines the path with the least driving time between them. The program should print both the list of cities on the path and the total time for the overall route.
