The problem You have been contracted to write a program that takes a list of the roads in service (and their distances) as input and then answers queries about the driving distance between any two Swamp county towns. The input will consist of a number of road-specification lines:
Starting Town Destination Town Distancefollowed by a number of query lines:
Starting Town Destination TownYour program should output one line per query line, indicating the shortest driving distance from the Starting Town to the Destination Town. You should assume that the driving distance from any town to itself is 0.
Input/Output Specification More precisely, the input file will consist of one or more road-specification lines, followed by a line with the single word queries, followed by one or more lines, each with two towns that appeared in the previous road-specifications. If the Destination Town is reachable from the Starting Town, your program should print the distance of the shortest path from the latter to the former. If the Destination Town is not reachable from the Starting Town, your program should print
Not Reachableinstead of the shortest distance. In each road-specification line the Starting Town and Destination Town will be strings of letters (whose first letter is capitalized) delimited by one or more spaces. All of the Distances in the read-specification lines will be integers, though not necessarily positive (or even nonnegative) integers -- in a place like Swamp County, time can swerve as unpredicatably as the drivers. No town name will be more than 50 letters long.
After all of the queries from a particular set of road-specifications, the line
end of querieswill appear, potentially followed by another problem instance. Your output should include a blank line to separate the output of different problem instances.
Albuquerque Baltimore 8 Albuquerque Chicago 13 Albuquerque Eastport 1 Baltimore Denver 6 Baltimore Eastport 12 Chicago Baltimore 9 Denver Albuquerque 7 Denver Chicago 0 Eastport Denver 11 Eastport Faraway 77 queries Albuquerque Denver Eastport Albuquerque Faraway Denver Baltimore Chicago end of queries Wallawalla Vancouver 8 queries Wallawalla Vancouver end of queries
12 18 Not Reachable 6 8