City Distance Map Database Design
I've never tried this but here's some ideas I have:

You'll need to keep track of all cities, so you will need a City table.
You also need to know the distance between two cities that are directly connected to each other, so you will need a cities_distances table like this:


cities_distances
----------------
  From_City_ID
  To_City_ID
  Distance


This will let you keep track of how much distance it is from one city to another. Note that this is directional - The distance from A to B might not be the same as from B to A if the highway between them has a lane for each direction, and one lane has a detour around some natural feature (like a small lake, or difficult parts of terrain). Within a city, this is also important because you'll have one-way streets. 

If you don't care about the direction of the distance between the two cities, you can just rename those two columsn CityA_ID and CityB_ID.

As for writing a query that gets the distance between any two cities, it might be easier to do that in code using Dijkstra's algorithm (because this is really just a graphing problem) than in query, but it might be possible using recursive queries. Or, you could generate a pre-calculated table that stores all this information and just look the data up in that.