### Fourni : Une implémentation des files de priorité
def file_prio():
    return []

def est_vide(f):
    return f == file_prio()

def enfiler_ou_maj(f, x, nouvelle_prio):
    for i in range(len(f)):
        (y, autre_prio) = f[i]
        if x == y:
            if nouvelle_prio < autre_prio:
                f[i] = (x, nouvelle_prio)
            return
    # Si x n'était pas dans la file, on le rajoute
    f.append((x, nouvelle_prio))

def defiler(f):
    x_candidat = None
    prio_candidat = None
    for (x, p) in f:
        if prio_candidat == None or p < prio_candidat:
            x_candidat = x
            prio_candidat = p
    f.remove((x_candidat, prio_candidat))
    return (x_candidat, prio_candidat)

### Données du métro de Paris (en fin de fichier)

# Trois variables très longues sont définies en fin de fichier:
# + La variable graphe contient le dictionnaire de
#   listes d'adajacence des sommets du métro de Paris
# + La variable noms contient un dictionnaire
#   des noms des différents sommets
# + La variable coords contient un dictionnaire
#   avec les coordonnées des différents arrêts
#   dans un certain repère cartésien.
#   Dans ce repère, chaque unité représente 25,7 mètres

### Algortihme de Dijkstra
def dijkstra(depart):
    res = {}
    a_visiter = file_prio()
    enfiler_ou_maj(a_visiter, depart, 0)
    while not est_vide(a_visiter):
        (u, d) = defiler(a_visiter)
        res[u] = d
        for (voisin, delta) in graphe[u]:
            if not (voisin in res):
                enfiler_ou_maj(a_visiter, voisin, d+delta)
    return res

### Exercice 1
def vol_oiseau(depart, arrivee):
    pass # TODO

### Exercice 2
def a_etoile(depart, arrivee):
    pass # TODO

### Exercice 3

# À propos de A*,
# je conjecture qu...

### Exercice 4
def dijkstra_nombre(depart, arrivee):
    pass # TODO

def a_etoile_nombre(depart, arrivee):
    pass # TODO

# Je constate que par rapport à l'algorithme de Dijkstra,
# l'algorithme A* ...

### Exercice 5

# TODO

### Données du métro de paris
graphe = {
    0: [(238, 41.0), (159, 46.0)],
    1: [(12, 36.0), (235, 44.0)],
    2: [(110, 69.0), (139, 50.0)],
    3: [(262, 33.0), (210, 41.0)],
    4: [(171, 43.0), (251, 35.0)],
    5: [(13, 67.0), (239, 54.0)],
    6: [(55, 56.0), (258, 46.0)],
    7: [(290, 39.0), (311, 79.0), (8, 120.0)],
    8: [(350, 38.0), (309, 58.0), (7, 120.0)],
    9: [(338, 28.0), (78, 62.0)],
    10: [(277, 42.0), (108, 36.0)],
    11: [(154, 32.0), (54, 41.0)],
    12: [(213, 42.0), (1, 36.0)],
    13: [(151, 57.0), (5, 67.0), (14, 120.0)],
    14: [(124, 46.0), (64, 28.0), (13, 120.0)],
    15: [(318, 37.0), (319, 73.0)],
    16: [(119, 98.0), (331, 62.0), (18, 120.0), (17, 120.0)],
    17: [(288, 89.0), (40, 41.0), (18, 120.0), (16, 120.0)],
    18: [(163, 32.0), (61, 56.0), (16, 120.0), (17, 120.0)],
    19: [(236, 31.0), (93, 33.0)],
    20: [(129, 48.0), (283, 38.0), (21, 120.0)],
    21: [(86, 46.0), (75, 51.0), (20, 120.0)],
    22: [(84, 39.0), (120, 81.0), (23, 120.0)],
    23: [(97, 35.0), (287, 57.0), (22, 120.0)],
    24: [(84, 51.0)],
    25: [(193, 42.0), (253, 35.0)],
    26: [(98, 31.0), (230, 64.0)],
    27: [(239, 64.0), (246, 59.0)],
    28: [(29, 79.0)],
    29: [(374, 46.0), (28, 79.0)],
    374: [(29, 46.0), (134, 53.0)],
    30: [(354, 24.0), (150, 44.0)],
    31: [(41, 28.0), (144, 36.0)],
    32: [(343, 54.0), (303, 41.0), (33, 120.0)],
    33: [(344, 52.0), (304, 41.0), (32, 120.0)],
    34: [(248, 36.0), (41, 57.0)],
    35: [(111, 34.0), (172, 40.0)],
    36: [(198, 105.0), (37, 39.0)],
    37: [(36, 39.0)],
    38: [(336, 35.0), (289, 38.0)],
    39: [(153, 38.0), (267, 46.0)],
    40: [(17, 41.0), (297, 37.0)],
    41: [(34, 57.0), (31, 28.0)],
    42: [(190, 42.0), (215, 35.0)],
    43: [(66, 41.0), (328, 57.0)],
    44: [(162, 54.0), (250, 64.0)],
    45: [(348, 43.0), (155, 35.0)],
    46: [(242, 63.0), (329, 46.0)],
    47: [(148, 46.0), (195, 41.0)],
    48: [(182, 66.0), (318, 60.0)],
    49: [(164, 42.0), (241, 40.0)],
    50: [(77, 54.0), (109, 62.0), (51, 120.0)],
    51: [(137, 62.0), (202, 69.0), (50, 120.0)],
    52: [(201, 20.0)],
    53: [(372, 47.0), (167, 33.0)],
    54: [(11, 41.0), (145, 51.0)],
    55: [(127, 60.0), (6, 56.0), (57, 120.0), (56, 120.0)],
    56: [(351, 59.0), (362, 75.0), (57, 120.0), (55, 120.0)],
    57: [(150, 35.0), (55, 120.0), (56, 120.0)],
    58: [(307, 31.0), (369, 31.0)],
    59: [(224, 72.0), (162, 53.0), (60, 120.0)],
    60: [(299, 63.0), (133, 45.0), (59, 120.0)],
    61: [(18, 56.0), (335, 28.0)],
    62: [(287, 53.0), (216, 48.0)],
    63: [(123, 44.0), (169, 57.0)],
    64: [(14, 28.0), (192, 57.0)],
    65: [(342, 41.0), (121, 57.0)],
    66: [(43, 41.0)],
    67: [(135, 87.0), (173, 51.0), (69, 120.0), (68, 120.0),
         (70, 120.0), (71, 120.0)],
    68: [(136, 85.0), (69, 120.0), (70, 120.0), (71, 120.0),
         (67, 120.0)],
    69: [(120, 287.0), (281, 131.0), (67, 120.0), (70, 120.0),
         (71, 120.0), (68, 120.0)],
    70: [(73, 45.0), (165, 66.0), (71, 120.0), (69, 120.0),
         (68, 120.0), (67, 120.0)],
    71: [(254, 73.0), (255, 37.0), (70, 120.0), (69, 120.0),
         (68, 120.0), (67, 120.0)],
    72: [(188, 52.0)],
    73: [(330, 46.0), (70, 45.0)],
    74: [(195, 44.0), (221, 52.0)],
    75: [(21, 51.0), (142, 93.0)],
    76: [(156, 59.0), (111, 30.0)],
    77: [(356, 57.0), (50, 54.0), (79, 120.0), (78, 120.0)],
    78: [(9, 62.0), (175, 41.0), (79, 120.0), (77, 120.0)],
    79: [(177, 41.0), (138, 71.0), (77, 120.0), (78, 120.0)],
    80: [(274, 41.0), (360, 49.0)],
    81: [(178, 43.0), (274, 43.0)],
    82: [(87, 32.0), (277, 47.0)],
    83: [(243, 36.0), (128, 49.0)],
    84: [(24, 51.0), (22, 39.0)],
    85: [(204, 47.0), (351, 46.0)],
    86: [(211, 37.0), (21, 46.0)],
    87: [(300, 43.0), (82, 32.0)],
    88: [(181, 44.0), (301, 47.0)],
    89: [(90, 29.0)],
    90: [(89, 29.0), (91, 26.0)],
    91: [(90, 26.0), (185, 27.0)],
    92: [(34, 37.0)],
    93: [(19, 33.0), (97, 45.0), (94, 120.0)],
    94: [(200, 27.0), (205, 39.0), (93, 120.0)],
    95: [(210, 48.0), (292, 37.0), (96, 120.0)],
    96: [(324, 52.0), (293, 42.0), (95, 120.0)],
    97: [(93, 45.0), (23, 35.0)],
    98: [(155, 69.0), (26, 31.0)],
    99: [(358, 31.0), (349, 54.0), (100, 120.0)],
    100: [(207, 113.0), (321, 59.0), (99, 120.0)],
    101: [(293, 43.0), (209, 36.0)],
    102: [(252, 35.0), (130, 37.0)],
    103: [(327, 44.0), (367, 30.0)],
    104: [(199, 62.0), (271, 40.0)],
    105: [(296, 42.0), (163, 47.0)],
    106: [(231, 29.0), (206, 36.0)],
    107: [(335, 49.0), (314, 49.0)],
    108: [(10, 36.0), (152, 29.0)],
    109: [(50, 62.0), (127, 59.0), (110, 120.0)],
    110: [(332, 37.0), (2, 69.0), (109, 120.0)],
    111: [(76, 30.0), (35, 34.0)],
    112: [(180, 71.0)],
    113: [(234, 36.0), (207, 47.0)],
    114: [(263, 72.0)],
    115: [(263, 39.0), (285, 70.0), (116, 120.0)],
    116: [(233, 50.0), (115, 120.0)],
    117: [(148, 59.0), (118, 120.0)],
    118: [(329, 60.0), (288, 30.0), (117, 120.0)],
    119: [(295, 41.0), (16, 98.0), (120, 120.0)],
    120: [(22, 81.0), (69, 287.0), (119, 120.0)],
    121: [(65, 57.0), (124, 67.0), (123, 120.0), (122, 120.0)],
    122: [(140, 103.0), (125, 59.0), (123, 120.0), (121, 120.0)],
    123: [(250, 51.0), (63, 44.0), (121, 120.0), (122, 120.0)],
    124: [(121, 67.0), (14, 46.0), (125, 120.0)],
    125: [(122, 59.0), (340, 107.0), (124, 120.0)],
    126: [(272, 37.0), (182, 42.0)],
    127: [(109, 59.0), (55, 60.0)],
    128: [(83, 49.0), (324, 42.0)],
    129: [(311, 49.0), (20, 48.0)],
    130: [(102, 37.0)],
    131: [(153, 72.0), (272, 63.0)],
    132: [(223, 68.0), (327, 40.0), (133, 120.0)],
    133: [(60, 45.0), (317, 49.0), (132, 120.0)],
    134: [(270, 47.0), (374, 53.0)],
    135: [(331, 65.0), (67, 87.0), (136, 120.0)],
    136: [(68, 85.0), (290, 73.0), (135, 120.0)],
    137: [(359, 54.0), (51, 62.0), (138, 120.0)],
    138: [(79, 71.0), (158, 57.0), (137, 120.0)],
    139: [(2, 50.0), (355, 46.0)],
    140: [(313, 47.0), (122, 103.0)],
    141: [(291, 37.0), (197, 49.0)],
    142: [(75, 93.0), (339, 27.0), (144, 120.0), (143, 120.0)],
    143: [(340, 29.0), (160, 44.0), (144, 120.0), (142, 120.0)],
    144: [(31, 36.0), (170, 46.0), (142, 120.0), (143, 120.0)],
    145: [(54, 51.0), (373, 55.0)],
    146: [(283, 33.0), (247, 50.0)],
    147: [(159, 44.0), (191, 49.0)],
    148: [(117, 59.0), (47, 46.0), (149, 120.0)],
    149: [(241, 57.0), (345, 79.0), (148, 120.0)],
    150: [(30, 44.0), (57, 35.0)],
    151: [(339, 93.0), (13, 57.0)],
    152: [(108, 29.0)],
    153: [(245, 64.0), (131, 72.0), (39, 38.0)],
    154: [(349, 33.0), (11, 32.0), (156, 120.0), (155, 120.0)],
    155: [(45, 35.0), (98, 69.0), (156, 120.0), (154, 120.0)],
    156: [(371, 46.0), (76, 59.0), (154, 120.0), (155, 120.0)],
    157: [(306, 36.0), (291, 49.0)],
    158: [(138, 57.0), (371, 66.0)],
    159: [(0, 46.0), (147, 44.0)],
    160: [(143, 44.0), (226, 40.0)],
    161: [(364, 28.0), (184, 39.0)],
    162: [(59, 53.0), (44, 54.0)],
    163: [(105, 47.0), (18, 32.0)],
    164: [(244, 60.0), (49, 42.0)],
    165: [(70, 66.0), (375, 33.0)],
    166: [(258, 38.0), (252, 37.0)],
    167: [(53, 33.0), (265, 31.0)],
    168: [(326, 49.0), (245, 28.0)],
    169: [(63, 57.0), (341, 54.0), (170, 120.0)],
    170: [(144, 46.0), (169, 120.0)],
    171: [(264, 49.0), (4, 43.0)],
    172: [(35, 40.0), (240, 35.0)],
    173: [(67, 51.0), (227, 34.0)],
    174: [(221, 31.0), (346, 72.0)],
    175: [(78, 41.0), (325, 144.0), (177, 120.0), (176, 120.0)],
    176: [(281, 71.0), (177, 120.0), (175, 120.0)],
    177: [(225, 88.0), (79, 41.0), (175, 120.0), (176, 120.0)],
    178: [(81, 43.0)],
    179: [(237, 37.0)],
    180: [(267, 91.0), (112, 71.0)],
    181: [(88, 44.0)],
    182: [(126, 42.0), (48, 66.0)],
    183: [(278, 51.0)],
    184: [(260, 31.0), (161, 39.0), (352, 36.0)],
    185: [(91, 27.0), (186, 26.0)],
    186: [(185, 26.0), (372, 33.0)],
    187: [(188, 34.0), (273, 46.0)],
    188: [(72, 52.0), (187, 34.0)],
    189: [(367, 49.0), (370, 35.0)],
    190: [(269, 27.0), (42, 42.0)],
    191: [(147, 49.0), (194, 67.0), (192, 120.0)],
    192: [(64, 57.0), (337, 36.0), (191, 120.0)],
    193: [(271, 38.0), (25, 42.0)],
    194: [(191, 67.0), (276, 67.0)],
    195: [(47, 41.0), (74, 44.0)],
    196: [(259, 47.0), (197, 120.0)],
    197: [(141, 49.0), (199, 28.0), (196, 120.0)],
    198: [(52, 42.0), (199, 120.0)],
    199: [(197, 28.0), (104, 62.0), (198, 120.0)],
    200: [(257, 51.0), (94, 27.0)],
    201: [(145, 46.0)],
    202: [(51, 69.0), (326, 112.0), (203, 120.0)],
    203: [(317, 53.0), (332, 40.0), (202, 120.0)],
    204: [(366, 51.0), (85, 47.0)],
    205: [(94, 39.0), (296, 38.0)],
    206: [(106, 36.0), (218, 45.0), (208, 120.0), (207, 120.0),
          (209, 120.0)],
    207: [(113, 47.0), (100, 113.0), (208, 120.0), (209, 120.0),
          (206, 120.0)],
    208: [(361, 42.0), (333, 48.0), (206, 120.0), (209, 120.0),
          (207, 120.0)],
    209: [(101, 36.0), (232, 54.0), (208, 120.0), (207, 120.0),
          (206, 120.0)],
    210: [(3, 41.0), (95, 48.0)],
    211: [(284, 49.0), (86, 37.0)],
    212: [(275, 86.0), (295, 64.0), (214, 120.0), (213, 120.0),
          (215, 120.0)],
    213: [(12, 42.0), (214, 120.0), (215, 120.0), (212, 120.0)],
    214: [(236, 42.0), (212, 120.0), (215, 120.0), (213, 120.0)],
    215: [(42, 35.0), (307, 60.0), (214, 120.0),
          (213, 120.0), (212, 120.0)],
    216: [(62, 48.0), (243, 55.0)],
    217: [(353, 29.0), (322, 37.0)],
    218: [(206, 45.0), (294, 38.0)],
    219: [(297, 50.0), (313, 81.0), (220, 120.0)],
    220: [(316, 35.0), (315, 80.0), (219, 120.0)],
    221: [(74, 52.0), (174, 31.0), (222, 120.0)],
    222: [(323, 42.0), (330, 31.0), (221, 120.0)],
    223: [(289, 43.0), (132, 68.0), (225, 120.0), (224, 120.0)],
    224: [(282, 80.0), (59, 72.0), (225, 120.0), (223, 120.0)],
    225: [(298, 75.0), (177, 88.0), (223, 120.0), (224, 120.0)],
    226: [(160, 40.0), (270, 39.0)],
    227: [(173, 34.0), (356, 38.0), (228, 120.0)],
    228: [(255, 53.0), (282, 49.0), (227, 120.0)],
    229: [(305, 43.0), (312, 64.0)],
    230: [(26, 64.0), (354, 62.0)],
    231: [(368, 40.0), (106, 29.0), (232, 120.0)],
    232: [(209, 54.0), (348, 46.0), (231, 120.0)],
    233: [(320, 33.0), (116, 50.0)],
    234: [(249, 38.0), (113, 36.0)],
    235: [(1, 44.0), (284, 44.0)],
    236: [(214, 42.0), (19, 31.0)],
    237: [(179, 37.0), (261, 37.0)],
    238: [(322, 27.0), (0, 41.0), (239, 120.0)],
    239: [(5, 54.0), (27, 64.0), (238, 120.0)],
    240: [(172, 35.0)],
    241: [(49, 40.0), (149, 57.0)],
    242: [(46, 63.0), (244, 120.0), (243, 120.0)],
    243: [(216, 55.0), (83, 36.0), (244, 120.0), (242, 120.0)],
    244: [(352, 37.0), (164, 60.0), (242, 120.0), (243, 120.0)],
    245: [(168, 28.0), (153, 64.0), (246, 120.0)],
    246: [(27, 59.0), (302, 37.0), (245, 120.0)],
    247: [(146, 50.0), (357, 23.0), (248, 120.0)],
    248: [(280, 57.0), (247, 120.0)],
    249: [(273, 35.0), (234, 38.0)],
    250: [(44, 64.0), (123, 51.0)],
    251: [(4, 35.0)],
    252: [(166, 37.0), (102, 35.0)],
    253: [(25, 35.0)],
    254: [(345, 75.0), (71, 73.0)],
    255: [(71, 37.0), (228, 53.0)],
    256: [(362, 37.0)],
    257: [(265, 26.0), (200, 51.0)],
    258: [(6, 46.0), (166, 38.0)],
    259: [(198, 47.0), (36, 84.0)],
    260: [(266, 37.0), (184, 31.0)],
    261: [(237, 37.0), (266, 46.0)],
    262: [(3, 33.0)],
    263: [(114, 72.0), (115, 39.0)],
    264: [(286, 41.0), (171, 49.0)],
    265: [(167, 31.0), (257, 26.0)],
    266: [(261, 46.0), (260, 37.0)],
    267: [(39, 46.0), (180, 91.0)],
    268: [(337, 39.0)],
    269: [(301, 35.0), (190, 27.0)],
    270: [(226, 39.0), (134, 47.0)],
    271: [(104, 40.0), (193, 38.0)],
    272: [(131, 63.0), (126, 37.0)],
    273: [(187, 46.0), (249, 35.0)],
    274: [(81, 43.0), (80, 41.0)],
    275: [(328, 41.0), (212, 86.0)],
    276: [(194, 67.0)],
    277: [(82, 47.0), (10, 42.0)],
    278: [(357, 59.0), (183, 51.0), (279, 120.0)],
    279: [(320, 37.0), (278, 120.0)],
    280: [(92, 43.0)],
    281: [(69, 131.0), (176, 71.0), (282, 120.0)],
    282: [(228, 49.0), (224, 80.0), (281, 120.0)],
    283: [(20, 38.0), (146, 33.0)],
    284: [(235, 44.0), (211, 49.0), (285, 120.0)],
    285: [(115, 70.0), (305, 61.0), (284, 120.0)],
    286: [(370, 35.0), (264, 41.0)],
    287: [(23, 57.0), (62, 53.0)],
    288: [(118, 30.0), (17, 89.0)],
    289: [(38, 38.0), (223, 43.0)],
    290: [(136, 73.0), (7, 39.0)],
    291: [(157, 49.0), (141, 37.0)],
    292: [(95, 37.0), (361, 38.0), (293, 120.0)],
    293: [(96, 42.0), (101, 43.0), (292, 120.0)],
    294: [(218, 38.0), (347, 46.0)],
    295: [(212, 64.0), (119, 41.0), (296, 120.0)],
    296: [(205, 38.0), (105, 42.0), (295, 120.0)],
    297: [(40, 37.0), (219, 50.0)],
    298: [(303, 46.0), (225, 75.0), (299, 120.0)],
    299: [(304, 48.0), (60, 63.0), (298, 120.0)],
    300: [(341, 46.0), (87, 43.0)],
    301: [(88, 47.0), (269, 35.0)],
    302: [(246, 37.0), (366, 53.0)],
    303: [(32, 41.0), (298, 46.0), (304, 120.0)],
    304: [(33, 41.0), (299, 48.0), (303, 120.0)],
    305: [(285, 61.0), (229, 43.0)],
    306: [(355, 33.0), (157, 36.0)],
    307: [(215, 60.0), (58, 31.0)],
    308: [(347, 29.0), (338, 33.0)],
    309: [(8, 58.0), (336, 65.0), (310, 120.0)],
    310: [(375, 28.0), (342, 67.0), (309, 120.0)],
    311: [(7, 79.0), (129, 49.0), (313, 120.0), (312, 120.0),
          (314, 120.0), (315, 120.0)],
    312: [(229, 64.0), (350, 37.0), (313, 120.0), (314, 120.0),
          (315, 120.0), (311, 120.0)],
    313: [(219, 81.0), (140, 47.0), (311, 120.0), (314, 120.0),
          (315, 120.0), (312, 120.0)],
    314: [(107, 49.0), (343, 98.0), (315, 120.0), (313, 120.0),
          (312, 120.0), (311, 120.0)],
    315: [(220, 80.0), (344, 107.0), (314, 120.0), (313, 120.0),
          (312, 120.0), (311, 120.0)],
    316: [(369, 27.0), (220, 35.0)],
    317: [(133, 49.0), (203, 53.0)],
    318: [(48, 60.0), (15, 37.0)],
    319: [(15, 73.0)],
    320: [(279, 37.0), (233, 33.0)],
    321: [(100, 59.0), (359, 23.0)],
    322: [(217, 37.0), (238, 27.0)],
    323: [(334, 47.0), (222, 42.0)],
    324: [(128, 42.0), (96, 52.0)],
    325: [(175, 144.0), (353, 69.0), (327, 120.0), (326, 120.0)],
    326: [(202, 112.0), (168, 49.0), (327, 120.0), (325, 120.0)],
    327: [(132, 40.0), (103, 44.0), (325, 120.0), (326, 120.0)],
    328: [(43, 57.0), (275, 41.0)],
    329: [(46, 46.0), (118, 60.0)],
    330: [(222, 31.0), (73, 46.0)],
    331: [(16, 62.0), (135, 65.0)],
    332: [(203, 40.0), (110, 37.0)],
    333: [(208, 48.0), (334, 32.0)],
    334: [(333, 32.0), (323, 47.0)],
    335: [(61, 28.0), (107, 49.0)],
    336: [(309, 65.0), (38, 35.0)],
    337: [(192, 36.0), (268, 39.0)],
    338: [(308, 33.0), (9, 28.0)],
    339: [(142, 27.0), (151, 93.0), (341, 120.0), (340, 120.0)],
    340: [(125, 107.0), (143, 29.0), (341, 120.0), (339, 120.0)],
    341: [(169, 54.0), (300, 46.0), (339, 120.0), (340, 120.0)],
    342: [(310, 67.0), (65, 41.0), (344, 120.0), (343, 120.0)],
    343: [(314, 98.0), (32, 54.0), (344, 120.0), (342, 120.0)],
    344: [(315, 107.0), (33, 52.0), (342, 120.0), (343, 120.0)],
    345: [(149, 79.0), (254, 75.0)],
    346: [(174, 72.0), (358, 33.0), (347, 120.0)],
    347: [(294, 46.0), (308, 29.0), (346, 120.0)],
    348: [(232, 46.0), (45, 43.0)],
    349: [(99, 54.0), (154, 33.0)],
    350: [(312, 37.0), (8, 38.0)],
    351: [(85, 46.0), (56, 59.0)],
    352: [(184, 36.0), (244, 37.0)],
    353: [(325, 69.0), (217, 29.0)],
    354: [(230, 62.0), (30, 24.0), (355, 120.0)],
    355: [(139, 46.0), (306, 33.0), (354, 120.0)],
    356: [(227, 38.0), (77, 57.0)],
    357: [(247, 23.0), (278, 59.0)],
    358: [(346, 33.0), (99, 31.0)],
    359: [(321, 23.0), (137, 54.0)],
    360: [(80, 49.0), (368, 47.0)],
    361: [(292, 38.0), (208, 42.0)],
    362: [(56, 75.0), (256, 37.0)],
    363: [(365, 28.0)],
    364: [(365, 28.0), (161, 28.0)],
    365: [(363, 28.0), (364, 28.0)],
    366: [(302, 53.0), (204, 51.0), (367, 120.0)],
    367: [(103, 30.0), (189, 49.0), (366, 120.0)],
    368: [(360, 47.0), (231, 40.0)],
    369: [(58, 31.0), (316, 27.0)],
    370: [(189, 35.0), (286, 35.0)],
    371: [(158, 66.0), (156, 46.0)],
    372: [(186, 33.0), (53, 47.0)],
    373: [(196, 37.0)],
    375: [(165, 33.0), (310, 28.0)]
}

noms = {
    0: 'Abbesses',
    1: 'Alexandre Dumas',
    2: 'Alma Marceau',
    3: 'Alésia',
    4: 'Anatole France',
    5: 'Anvers',
    6: 'Argentine',
    7: 'Arts et Métiers',
    8: 'Arts et Métiers',
    9: 'Assemblée Nationale',
    10: 'Aubervilliers-Pantin, Quatre Chemins',
    11: 'Avenue Émile Zola',
    12: 'Avron',
    13: 'Barbès Rochechouart',
    14: 'Barbès Rochechouart',
    15: 'Basilique de Saint-Denis',
    16: 'Bastille',
    17: 'Bastille',
    18: 'Bastille',
    19: 'Bel Air',
    20: 'Belleville',
    21: 'Belleville',
    22: 'Bercy',
    23: 'Bercy',
    24: 'Bibliothèque François Mitterand',
    25: 'Billancourt',
    26: 'Bir-Hakeim',
    27: 'Blanche',
    28: 'Bobigny, Pablo Picasso',
    29: 'Bobigny-Pantin, Raymond Queneau',
    30: 'Boissière',
    31: 'Bolivar',
    32: 'Bonne Nouvelle',
    33: 'Bonne Nouvelle',
    34: 'Botzaris',
    35: 'Boucicaut',
    36: 'Boulogne, Jean Jaurès',
    37: 'Boulogne, Pont de Saint-Cloud, Rond Point Rhin et Danube',
    38: 'Bourse',
    39: 'Brochant',
    40: 'Bréguet-Sabin',
    41: 'Buttes Chaumont',
    42: 'Buzenval',
    43: 'Bérault',
    44: 'Cadet',
    45: 'Cambronne',
    46: 'Campo-Formio',
    47: 'Cardinal Lemoine',
    48: 'Carrefour Pleyel',
    49: 'Censier Daubenton',
    50: 'Champs Élysées, Clémenceau',
    51: 'Champs Élysées, Clémenceau',
    52: 'Chardon Lagâche',
    53: 'Charenton-Écoles',
    54: 'Charles Michels',
    55: 'Charles de Gaulle, Étoile',
    56: 'Charles de Gaulle, Étoile',
    57: 'Charles de Gaulle, Étoile',
    58: 'Charonne',
    59: "Chaussée d'Antin, La Fayette",
    60: "Chaussée d'Antin, La Fayette",
    61: 'Chemin Vert',
    62: 'Chevaleret',
    63: 'Château Landon',
    64: 'Château Rouge',
    65: "Château d'Eau",
    66: 'Château de Vincennes',
    67: 'Châtelet',
    68: 'Châtelet',
    69: 'Châtelet',
    70: 'Châtelet',
    71: 'Châtelet',
    72: 'Châtillon-Montrouge',
    73: 'Cité',
    74: 'Cluny, La Sorbonne',
    75: 'Colonel Fabien',
    76: 'Commerce',
    77: 'Concorde',
    78: 'Concorde',
    79: 'Concorde',
    80: 'Convention',
    81: 'Corentin Celton',
    82: 'Corentin-Cariou',
    83: 'Corvisart',
    84: 'Cour Saint-Émilion',
    85: 'Courcelles',
    86: 'Couronnes',
    87: 'Crimée',
    88: 'Croix de Chavaux',
    89: 'Créteil-Préfecture',
    90: 'Créteil-Université',
    91: "Créteil-l'Echat, Hôpital Henri Mondor",
    92: 'Danube',
    93: 'Daumesnil',
    94: 'Daumesnil',
    95: 'Denfert Rochereau',
    96: 'Denfert Rochereau',
    97: 'Dugommier',
    98: 'Dupleix',
    99: 'Duroc',
    100: 'Duroc',
    101: 'Edgar Quinet',
    102: 'Esplanade de la Défense',
    103: 'Europe',
    104: 'Exelmans',
    105: 'Faidherbe-Chaligny',
    106: 'Falguière',
    107: 'Filles du Calvaire',
    108: "Fort d'Aubervilliers",
    109: 'Franklin D. Roosevelt',
    110: 'Franklin D. Roosevelt',
    111: 'Félix Faure',
    112: 'Gabriel Péri, Asnières-Gennevilliers',
    113: 'Gaité',
    114: 'Galliéni',
    115: 'Gambetta',
    116: 'Gambetta',
    117: "Gare d'Austerlitz",
    118: "Gare d'Austerlitz",
    119: 'Gare de Lyon',
    120: 'Gare de Lyon',
    121: "Gare de l'Est",
    122: "Gare de l'Est",
    123: "Gare de l'Est",
    124: 'Gare du Nord',
    125: 'Gare du Nord',
    126: 'Garibaldi',
    127: 'George V',
    128: 'Glacière',
    129: 'Goncourt',
    130: 'Grande Arche de la Défense',
    131: 'Guy Môquet',
    132: 'Havre Caumartin',
    133: 'Havre Caumartin',
    134: 'Hoche',
    135: 'Hôtel de Ville',
    136: 'Hôtel de Ville',
    137: 'Invalides',
    138: 'Invalides',
    139: 'Iéna',
    140: 'Jacques Bonsergent',
    141: 'Jasmin',
    142: 'Jaurès',
    143: 'Jaurès',
    144: 'Jaurès',
    145: 'Javel',
    146: 'Jourdain',
    147: 'Jules Joffrin',
    148: 'Jussieu',
    149: 'Jussieu',
    150: 'Kléber',
    151: 'La Chapelle',
    152: 'La Courneuve, 8 Mai 1945',
    153: 'La Fourche',
    154: 'La Motte Picquet, Grenelle',
    155: 'La Motte Picquet, Grenelle',
    156: 'La Motte Picquet, Grenelle',
    157: 'La Muette',
    158: 'La Tour-Maubourg',
    159: 'Lamarck Caulaincourt',
    160: 'Laumière',
    161: 'Le Kremlin-Bicêtre',
    162: 'Le Peletier',
    163: 'Ledru Rollin',
    164: 'Les Gobelins',
    165: 'Les Halles',
    166: 'Les Sablons',
    167: 'Liberté',
    168: 'Liège',
    169: 'Louis Blanc',
    170: 'Louis Blanc',
    171: 'Louise Michel',
    172: 'Lourmel',
    173: 'Louvre, Rivoli',
    174: 'Mabillon',
    175: 'Madeleine',
    176: 'Madeleine',
    177: 'Madeleine',
    178: "Mairie d'Issy",
    179: "Mairie d'Ivry",
    180: 'Mairie de Clichy',
    181: 'Mairie de Montreuil',
    182: 'Mairie de Saint-Ouen',
    183: 'Mairie des Lilas',
    184: 'Maison Blanche',
    185: 'Maisons-Alfort les Juilliottes',
    186: 'Maisons-Alfort, Stade',
    187: 'Malakoff-Plateau de Vanves',
    188: 'Malakoff-Rue Étienne Dolet',
    189: 'Malesherbes',
    190: 'Maraîchers',
    191: 'Marcadet Poissonniers',
    192: 'Marcadet Poissonniers',
    193: 'Marcel Sembat',
    194: 'Marx Dormoy',
    195: 'Maubert Mutualité',
    196: 'Michel Ange Auteuil',
    197: 'Michel Ange Auteuil',
    198: 'Michel Ange Molitor',
    199: 'Michel Ange Molitor',
    200: 'Michel Bizot',
    201: 'Mirabeau',
    202: 'Miromesnil',
    203: 'Miromesnil',
    204: 'Monceau',
    205: 'Montgallet',
    206: 'Montparnasse Bienvenue',
    207: 'Montparnasse Bienvenue',
    208: 'Montparnasse Bienvenue',
    209: 'Montparnasse Bienvenue',
    210: 'Mouton-Duvernet',
    211: 'Ménilmontant',
    212: 'Nation',
    213: 'Nation',
    214: 'Nation',
    215: 'Nation',
    216: 'Nationale',
    217: 'Notre Dame de Lorette',
    218: 'Notre-Dame-des-Champs',
    219: 'Oberkampf',
    220: 'Oberkampf',
    221: 'Odéon',
    222: 'Odéon',
    223: 'Opéra',
    224: 'Opéra',
    225: 'Opéra',
    226: 'Ourcq',
    227: 'Palais Royal, Musée du Louvre',
    228: 'Palais Royal, Musée du Louvre',
    229: 'Parmentier',
    230: 'Passy',
    231: 'Pasteur',
    232: 'Pasteur',
    233: 'Pelleport',
    234: 'Pernety',
    235: 'Philippe-Auguste',
    236: 'Picpus',
    237: 'Pierre Curie',
    238: 'Pigalle',
    239: 'Pigalle',
    240: 'Place Balard',
    241: 'Place Monge',
    242: "Place d'Italie",
    243: "Place d'Italie",
    244: "Place d'Italie",
    245: 'Place de Clichy',
    246: 'Place de Clichy',
    247: 'Place des Fêtes',
    248: 'Place des Fêtes',
    249: 'Plaisance',
    250: 'Poissonnière',
    251: 'Pont de Levallois, Bécon',
    252: 'Pont de Neuilly',
    253: 'Pont de Sèvres',
    254: 'Pont-Marie',
    255: 'Pont-Neuf',
    256: 'Porte Dauphine',
    257: 'Porte Dorée',
    258: 'Porte Maillot',
    259: "Porte d'Auteuil",
    260: "Porte d'Italie",
    261: "Porte d'Ivry",
    262: "Porte d'Orléans",
    263: 'Porte de Bagnolet',
    264: 'Porte de Champerret',
    265: 'Porte de Charenton',
    266: 'Porte de Choisy',
    267: 'Porte de Clichy',
    268: 'Porte de Clignancourt',
    269: 'Porte de Montreuil',
    270: 'Porte de Pantin',
    271: 'Porte de Saint-Cloud',
    272: 'Porte de Saint-Ouen',
    273: 'Porte de Vanves',
    274: 'Porte de Versailles',
    275: 'Porte de Vincennes',
    276: 'Porte de la Chapelle',
    277: 'Porte de la Villette',
    278: 'Porte des Lilas',
    279: 'Porte des Lilas',
    280: 'Pré-Saint-Gervais',
    281: 'Pyramides',
    282: 'Pyramides',
    283: 'Pyrénées',
    284: 'Père Lachaise',
    285: 'Père Lachaise',
    286: 'Péreire',
    287: 'Quai de la Gare',
    288: 'Quai de la Rapée',
    289: 'Quatre Septembre',
    290: 'Rambuteau',
    291: 'Ranelagh',
    292: 'Raspail',
    293: 'Raspail',
    294: 'Rennes',
    295: 'Reuilly Diderot',
    296: 'Reuilly Diderot',
    297: 'Richard Lenoir',
    298: 'Richelieu Drouot',
    299: 'Richelieu Drouot',
    300: 'Riquet',
    301: 'Robespierre',
    302: 'Rome',
    303: 'Rue Montmartre, Grands Boulevards',
    304: 'Rue Montmartre, Grands Boulevards',
    305: 'Rue Saint-Maur',
    306: 'Rue de la Pompe',
    307: 'Rue des Boulets',
    308: 'Rue du Bac',
    309: 'Réaumur Sébastopol',
    310: 'Réaumur Sébastopol',
    311: 'République',
    312: 'République',
    313: 'République',
    314: 'République',
    315: 'République',
    316: 'Saint-Ambroise',
    317: 'Saint-Augustin',
    318: 'Saint-Denis-Porte de Paris',
    319: 'Saint-Denis-Université',
    320: 'Saint-Fargeau',
    321: 'Saint-Francois Xavier',
    322: 'Saint-Georges',
    323: 'Saint-Germain-des-Prés',
    324: 'Saint-Jacques',
    325: 'Saint-Lazare',
    326: 'Saint-Lazare',
    327: 'Saint-Lazare',
    328: 'Saint-Mandé, Tourelle',
    329: 'Saint-Marcel',
    330: 'Saint-Michel',
    331: 'Saint-Paul, Le Marais',
    332: 'Saint-Philippe du Roule',
    333: 'Saint-Placide',
    334: 'Saint-Sulpice',
    335: 'Saint-Sébastien-Froissart',
    336: 'Sentier',
    337: 'Simplon',
    338: 'Solférino',
    339: 'Stalingrad',
    340: 'Stalingrad',
    341: 'Stalingrad',
    342: 'Strasbourg Saint-Denis',
    343: 'Strasbourg Saint-Denis',
    344: 'Strasbourg Saint-Denis',
    345: 'Sully Morland',
    346: 'Sèvres Babylone',
    347: 'Sèvres Babylone',
    348: 'Sèvres Lecourbe',
    349: 'Ségur',
    350: 'Temple',
    351: 'Ternes',
    352: 'Tolbiac',
    353: "Trinité d'Estienne d'Orves",
    354: 'Trocadéro',
    355: 'Trocadéro',
    356: 'Tuileries',
    357: 'Télégraphe',
    358: 'Vaneau',
    359: 'Varenne',
    360: 'Vaugirard',
    361: 'Vavin',
    362: 'Victor Hugo',
    363: 'Villejuif, Louis Aragon',
    364: 'Villejuif, Léo Lagrange',
    365: 'Villejuif, P. Vaillant Couturier',
    366: 'Villiers',
    367: 'Villiers',
    368: 'Volontaires',
    369: 'Voltaire',
    370: 'Wagram',
    371: 'École Militaire',
    372: 'École Vétérinaire de Maisons-Alfort',
    373: "Église d'Auteuil",
    374: 'Église de Pantin',
    375: 'Étienne Marcel'}

coords = {0: (308, 536),
          1: (472, 386),
          2: (193, 404),
          3: (290, 244),
          4: (138, 517),
          5: (324, 521),
          6: (149, 442),
          7: (374, 414),
          8: (373, 417),
          9: (258, 382),
          10: (433, 595),
          11: (194, 326),
          12: (472, 372),
          13: (350, 521),
          14: (350, 521),
          15: (343, 646),
          16: (403, 360),
          17: (403, 361),
          18: (403, 362),
          19: (471, 324),
          20: (428, 456),
          21: (428, 456),
          22: (437, 296),
          23: (437, 296),
          24: (424, 268),
          25: (77, 270),
          26: (172, 353),
          27: (278, 521),
          28: (522, 593),
          29: (498, 574),
          30: (160, 406),
          31: (426, 498),
          32: (339, 452),
          33: (340, 454),
          34: (457, 492),
          35: (185, 289),
          36: (79, 316),
          37: (67, 307),
          38: (314, 434),
          39: (249, 544),
          40: (408, 376),
          41: (435, 492),
          42: (477, 365),
          43: (532, 329),
          44: (322, 484),
          45: (217, 328),
          46: (376, 278),
          47: (350, 329),
          48: (314, 622),
          49: (356, 288),
          50: (237, 414),
          51: (237, 413),
          52: (134, 318),
          53: (483, 264),
          54: (178, 326),
          55: (170, 436),
          56: (170, 437),
          57: (170, 435),
          58: (442, 383),
          59: (284, 472),
          60: (284, 472),
          61: (397, 383),
          62: (404, 269),
          63: (384, 484),
          64: (350, 532),
          65: (364, 462),
          66: (547, 324),
          67: (324, 386),
          68: (324, 383),
          69: (323, 380),
          70: (324, 382),
          71: (322, 378),
          72: (229, 193),
          73: (317, 366),
          74: (319, 340),
          75: (416, 472),
          76: (196, 311),
          77: (257, 407),
          78: (258, 406),
          79: (256, 407),
          80: (202, 273),
          81: (192, 242),
          82: (422, 562),
          83: (355, 259),
          84: (439, 281),
          85: (202, 462),
          86: (439, 442),
          87: (419, 550),
          88: (523, 402),
          89: (529, 207),
          90: (522, 216),
          91: (516, 224),
          92: (468, 501),
          93: (461, 316),
          94: (461, 316),
          95: (300, 277),
          96: (302, 276),
          97: (448, 304),
          98: (180, 344),
          99: (238, 336),
          100: (238, 336),
          101: (276, 295),
          102: (91, 461),
          103: (242, 483),
          104: (112, 301),
          105: (432, 352),
          106: (253, 312),
          107: (397, 413),
          108: (438, 608),
          109: (214, 421),
          110: (214, 421),
          111: (192, 300),
          112: (198, 607),
          113: (259, 282),
          114: (527, 429),
          115: (484, 429),
          116: (484, 429),
          117: (389, 317),
          118: (389, 317),
          119: (428, 331),
          120: (418, 321),
          121: (367, 484),
          122: (368, 484),
          123: (367, 484),
          124: (364, 510),
          125: (369, 507),
          126: (281, 596),
          127: (192, 428),
          128: (337, 265),
          129: (413, 445),
          130: (77, 465),
          131: (267, 560),
          132: (268, 465),
          133: (268, 465),
          134: (468, 550),
          135: (356, 375),
          136: (356, 375),
          137: (237, 389),
          138: (237, 387),
          139: (175, 397),
          140: (386, 448),
          141: (129, 352),
          142: (415, 508),
          143: (416, 509),
          144: (416, 508),
          145: (158, 326),
          146: (449, 474),
          147: (331, 554),
          148: (367, 324),
          149: (367, 324),
          150: (166, 422),
          151: (372, 521),
          152: (441, 619),
          153: (259, 533),
          154: (205, 332),
          155: (204, 332),
          156: (203, 333),
          157: (139, 384),
          158: (220, 373),
          159: (314, 553),
          160: (430, 519),
          161: (385, 217),
          162: (301, 484),
          163: (415, 359),
          164: (353, 272),
          165: (337, 404),
          166: (118, 453),
          167: (475, 274),
          168: (258, 497),
          169: (402, 497),
          170: (402, 497),
          171: (154, 512),
          172: (173, 279),
          173: (305, 392),
          174: (288, 347),
          175: (258, 422),
          176: (258, 422),
          177: (257, 423),
          178: (187, 226),
          179: (439, 223),
          180: (215, 585),
          181: (537, 412),
          182: (294, 606),
          183: (518, 474),
          184: (386, 232),
          185: (509, 232),
          186: (503, 240),
          187: (239, 225),
          188: (236, 212),
          189: (213, 493),
          190: (490, 375),
          191: (350, 554),
          192: (350, 554),
          193: (90, 280),
          194: (376, 557),
          195: (335, 334),
          196: (123, 334),
          197: (123, 334),
          198: (119, 324),
          199: (119, 324),
          200: (468, 308),
          201: (141, 321),
          202: (237, 440),
          203: (237, 440),
          204: (216, 474),
          205: (452, 328),
          206: (266, 307),
          207: (263, 300),
          208: (267, 306),
          209: (263, 300),
          210: (295, 259),
          211: (448, 431),
          212: (464, 351),
          213: (466, 357),
          214: (463, 349),
          215: (466, 357),
          216: (389, 258),
          217: (289, 502),
          218: (278, 320),
          219: (417, 409),
          220: (419, 411),
          221: (300, 347),
          222: (300, 348),
          223: (284, 444),
          224: (284, 444),
          225: (284, 444),
          226: (442, 529),
          227: (292, 395),
          228: (293, 396),
          229: (421, 427),
          230: (157, 373),
          231: (243, 307),
          232: (243, 307),
          233: (489, 448),
          234: (254, 269),
          235: (471, 403),
          236: (473, 336),
          237: (430, 234),
          238: (303, 521),
          239: (303, 521),
          240: (162, 271),
          241: (360, 303),
          242: (368, 255),
          243: (368, 254),
          244: (368, 254),
          245: (259, 508),
          246: (259, 508),
          247: (467, 481),
          248: (467, 482),
          249: (249, 255),
          250: (347, 484),
          251: (125, 521),
          252: (104, 457),
          253: (66, 262),
          254: (349, 369),
          255: (308, 382),
          256: (134, 422),
          257: (478, 291),
          258: (132, 448),
          259: (105, 336),
          260: (394, 223),
          261: (419, 243),
          262: (285, 232),
          263: (499, 430),
          264: (172, 506),
          265: (470, 285),
          266: (405, 232),
          267: (238, 558),
          268: (350, 583),
          269: (498, 382),
          270: (454, 538),
          271: (101, 290),
          272: (275, 583),
          273: (245, 242),
          274: (197, 258),
          275: (496, 341),
          276: (384, 582),
          277: (429, 579),
          278: (498, 474),
          279: (498, 474),
          280: (484, 496),
          281: (284, 413),
          282: (284, 413),
          283: (439, 466),
          284: (460, 416),
          285: (460, 416),
          286: (187, 501),
          287: (420, 282),
          288: (393, 328),
          289: (300, 439),
          290: (365, 402),
          291: (133, 366),
          292: (292, 289),
          293: (291, 288),
          294: (271, 333),
          295: (442, 339),
          296: (442, 339),
          297: (412, 390),
          298: (307, 462),
          299: (307, 464),
          300: (414, 534),
          301: (509, 390),
          302: (248, 499),
          303: (324, 457),
          304: (325, 459),
          305: (437, 422),
          306: (144, 397),
          307: (449, 373),
          308: (258, 358),
          309: (351, 422),
          310: (351, 422),
          311: (398, 433),
          312: (397, 433),
          313: (398, 434),
          314: (395, 432),
          315: (399, 435),
          316: (428, 401),
          317: (254, 452),
          318: (332, 637),
          319: (365, 664),
          320: (494, 460),
          321: (237, 359),
          322: (300, 511),
          323: (284, 352),
          324: (321, 269),
          325: (259, 478),
          326: (258, 478),
          327: (258, 477),
          328: (511, 336),
          329: (381, 295),
          330: (312, 349),
          331: (380, 367),
          332: (225, 430),
          333: (272, 324),
          334: (275, 336),
          335: (397, 394),
          336: (327, 430),
          337: (350, 568),
          338: (258, 371),
          339: (408, 516),
          340: (409, 518),
          341: (408, 517),
          342: (359, 447),
          343: (359, 445),
          344: (359, 447),
          345: (374, 354),
          346: (260, 347),
          347: (260, 347),
          348: (232, 321),
          349: (217, 336),
          350: (384, 427),
          351: (188, 451),
          352: (376, 242),
          353: (280, 495),
          354: (157, 397),
          355: (157, 397),
          356: (278, 400),
          357: (476, 480),
          358: (248, 343),
          359: (237, 368),
          360: (217, 285),
          361: (282, 300),
          362: (148, 418),
          363: (385, 184),
          364: (385, 206),
          365: (385, 195),
          366: (232, 486),
          367: (231, 487),
          368: (231, 297),
          369: (435, 393),
          370: (200, 497),
          371: (209, 350),
          372: (495, 250),
          373: (137, 330),
          374: (484, 563),
          375: (347, 412)}