Where to get the distance between cities if the number of combinations is more than 100,000?

Question

Google Maps

Hello!
There are 500+ cities (Russia and CIS), you need to calculate the distance between cities. You need to make a combination of each with each. To be more clear.

1. Moscow
2. St. Petersburg
3. Yekaterinburg

1. Moscow - St. Petersburg (aka St. Petersburg - Moscow)
2. Moscow - Yekaterinburg (aka Yekaterinburg - Moscow)
3. St. Petersburg - Yekaterinburg (aka Yekaterinburg - St. Petersburg)

If I'm not mistaken, then in combinatorics this is a combination formula without repetitions, which is approximately equal to 100,000 combinations.
With limits in Google Maps Distance Matrix of 2500 requests per day, I will have to collect this data for 40 days, which, of course, is a very long time.
The only viable option suggests itself: you can collect the coordinates of cities (500 requests), and calculate the distance between them using a formula. In fact, it does not matter how to calculate (GC, or Rhumb Line), as it is actually clear, we are laying on the roads or directly through the air.
Question: are there any ways to calculate the distance faster and easier (API without limits) than the option I proposed ?

Answer 1

https://en.wikipedia.org/wiki/Vincenty%27s_formulae
https://pypi.python.org/pypi/vincenty/0.1.4
https://pypi.python.org/pypi/geopy