Beräkna avstånd mellan 400 städer och optimera MySQL för det?

Jag såg två möjliga lösningar.

Första:
För varje stadsbutik i databasen dess latitud och longitud; när användaren får en fråga, beräknar du avstånd med varannan stad och returnerar resultat.
Fördelen är att du kan lägga till varje stad i db utan att behöva lägga till annan information.
Här du kan även hitta formler, exempel och kod för latitud-longitud avstånd beräkna...

Andra:
Skapa en tabell cities_dist med tre fält:city1_id, city2_id, distance och sätt in alla möjliga kombinationer bland dina städer. Med det kan du skriva en fråga med vald stad som är city1_id eller city2_id.
Prov är att du kan använda en enkel fråga utan någon beräkning, medan nackdelarna är att du måste fylla i denna tabell när du infogar en ny stad i din databas.

REDIGERAD efter användarkommentar:
Föreställ dig att du har tre städer

ID  NAME
1   New York
2   Rome
3   Berlin

Den tabellen borde se ut

CITY1  CITY2  DIST
1      2      1500
1      3      1200
2      3       400

När en användare vill flyga från Berlin kan du använda

SELECT c1.name, c2.name, cd.dist 
FROM cities_dist cd
  INNER JOIN cities c1 ON cd.city1 = c1.id
  INNER JOIN cities c2 ON cd.city2 = c2.id
WHERE cd.city1 = your_id
   OR cd.city2 = your_id
ORDER BY cd.dist ASC