You have to come up with some added, unnecessary, implementation-exposing abstraction like "CityPair". (In which case "delete" could be ill-defined if, as would be wise, the distance is computed from a lat/long or road table lookup, and so there is no actual database entry that corresponds to the distance between the cities.) That's the problem with REST: it doesn't avoid the complexity of RPC; it just crams it into ever-more-creative resource types.
Most API users (sorry, "consumers") would prefer they just be told the format in which to ask for the data, not have to re-discover it through gradually-exposed paths each time.