Fast Code Challenge 2

FastCode.txt

s maximum pour trouver une solution : 240:00
  
	
La région Loire-Atlantique a décidé d'ouvrir une grande quantité de données publiques.

Parmi celles-ci, la liste des arrêts, horaires et circuits TAN (Transports de l'Agglomération Nantaise). La région veut mettre à disposition des utilisateurs TAN un outil permettant de calculer le chemin le plus court entre deux arrêts en utilisant le réseau TAN.
 

En entrée de votre programme sont fournies les données dont vous avez besoin, au format ASCII :​

    L'arrêt de départ de l'itinéraire
    L'arrêt d'arrivée de l'itinéraire
    La liste de tous les arrêts
    Les liaisons entre arrêts

Liste de tous les arrêts :
Une suite de lignes représentant les arrêts (un arrêt par ligne) et contenant les champs suivants :

    L'identifiant unique de l'arrêt
    Le nom complet de l'arrêt entouré du caractère guillemet "
    La description de l'arrêt (non utilisée)
    La latitude de l'arrêt (en degrés)
    La longitude de l'arrêt (en degrés)
    L'identifiant de la zone (non utilisé)
    L'url de l'arrêt (non utilisée)
    Le type d'arrêt
    La station parente (non utilisée)

Ces champs sont séparés par une virgule ,

Exemple :
StopArea:ABDU,"Abel Durand",,47.22019661,-1.60337553,,,1,

Les liaisons entre arrêts :
Une liste de lignes représentant les liaisons entre arrêts (une liaison par ligne). Chacune de ces lignes contient deux identifiants d'arrêt séparés par un espace.
​
Chaque ligne représente une liaison uni-directionnelle allant du premier identifiant vers le second.
Si deux arrêts A et B sont réciproquement accessibles, il y aura donc deux lignes pour représenter cette liaison :
A B
B A

Exemple :
StopArea:LAIL StopArea:GALH
StopArea:GALH StopArea:LAIL

DISTANCE
Le programme devra renvoyer le chemin le plus court en terme de distance en respectant les contraintes de liaisons entre arrêts.

​La distance entre deux arrêts A et B sera calculée en utilisant la formule suivante :​
​
Note : Dans cette formule, les latitudes et longitu​des sont exprimées en radians. 6371 correspond au rayon de la terre en km.

Le programme affichera la liste des noms complets des arrêts par lesquels passe le chemin le plus court.
Si aucun chemin n'est possible entre l'arrêt de départ et d'arrivée, le programme affichera IMPOSSIBLE.
 
ENTRÉE :
Ligne 1 : l'identifiant de l'arrêt de départ
Ligne 2 : l'identifiant de l'arrêt d'arrivée
Ligne 3 : le nombre N d'arrêts du réseau TAN
N Lignes suivantes : les N arrêts (format décrit plus haut)
Ligne suivante : le nombre M de liaisons du réseau TAN
M Lignes suivantes : les M liaisons (format décrit plus haut)

SORTIE :
La liste des noms complets d'arrêts (un nom par ligne) par lesquels passe le plus court chemin du départ à l'arrivée (départ et arrivées inclus)
Ces noms ne doivent pas être entourés par le caractère guillement ".
S'il est impossible de trouver un chemin entre le départ et l'arrivée, le programme devra afficher IMPOSSIBLE.
 
CONTRAINTES :
0 < N < 10000
0 < M < 10000
 
EXEMPLE :
Entrée
StopArea:ABDU
StopArea:ABLA
3
StopArea:ABDU,"Abel Durand",,47.22019661,-1.60337553,,,1,
StopArea:ABLA,"Avenue Blanche",,47.22973509,-1.58937990,,,1,
StopArea:ACHA,"Angle Chaillou",,47.26979248,-1.57206627,,,1,
2
StopArea:ABDU StopArea:ABLA
StopArea:ABLA StopArea:ACHA
Sortie
Abel Durand
Avenue Blanche
Mémoire RAM disponible : 256Mo
Durée maximum d’exécution : 2 secondes

    Le programme doit lire les entrées depuis l’entrée standard
    Le programme doit écrire la réponse dans la sortie standard
    Le programme doit fonctionner dans l’environnement de test fourni

Fichiers fournis dans le script de test :
Exemple : in1.txt out1.txt
Un seul arrêt : in2.txt out2.txt
Même départ et arrivée : in3.txt out3.txt
Plusieurs étapes : in4.txt out4.txt
Grand nombre d'étapes : in5.txt out5.txt
Chemin impossible : in6.txt out6.txtv