Aidons la DDT! - Lycée Marguerite de Navarre (Bourges)

On considère n villes situées situées sur un plan euclidien. Chaque ville est identifiée par une lettre et des coordonnées. On souhaite relier toutes les villes entre elles. Pour ce faire, on peut construire des routes et des ronds-points sachant que les coûts sont les suivants :
Route : 1 000 000 € le km linéaire ;
Rond-point : 1 000 000 € l’unité.
Il n’y a pas de limite au nombre de routes se rencontrant à un rond-point.
Comment relier les n villes pour minimiser le coût global ?