from math import asin,cos,sin,sqrt,pi

# la ligne suivante a un chemin absolu : à adapter
# selon la machine.
fichier = open("/User/User/Documents/metro.csv","r",encoding = "utf-8")

# création d'un dictionnaire :
# ligne["4"] contient une liste des différentes
# stations de la ligne dans l'ordre de la ligne.
# Les clés sont bien des strings.
# Regardez les clés du dictionnaire pour voir
# les lignes disponibles.

temp = fichier.readlines()
ligne = {}
for l in temp:
    temp2 = l[:-1].split(";")
    ligne[temp2[0]] = temp2[1:]
fichier.close()

# création d'un second dictionnaire :
# position["Les Halles"] contient un couple
# (latitude,longitude) de sa position.
# Pas d'inquiétude, vous n'aurez pas à comprendre
# ce qu'est la latitude / longitude pour ce TP.

fichier = open("/User/User/Documents/positions.csv","r",encoding = "utf-8")
temp = fichier.readlines()
position = {}
for l in temp:
    temp2 = l.split(";")
    position[temp2[0]] = float(temp2[1]),float(temp2[2])
fichier.close()



def distance_vol_oiseau(p1,p2):
# calcule une distance entre deux couples
# (latitude, longitude) (donc entre deux valeurs
# de position)
    phi1,l1 = p1
    phi1,l1 = phi1/180*pi,l1/180*pi
    phi2,l2 = p2
    phi2,l2 = phi2/180*pi,l2/180*pi
    RT = 6371000
    s = sin((l2-l1)/2)**2
    c = sin((phi2-phi1)/2)**2*cos(l1)*cos(l2)
    return 2*RT*asin(sqrt(s+c))

# Initialisation du dictionnaire distance.
# À vous de remplir !
distance = {x : {} for x in position}


def dijkstra(origine):
# Je vous donne les initialisations :
# c'est comme d'habitude, mais avec des dicos.
    d = {x : float("inf") for x in position}
    d[origine] = 0
    n = len(d)
    T = {x : False for x in position}
    chemin = {origine : [origine]}