Voir les cours et résoudre les problèmes en :
Le C est un langage de programmation impératif conçu pour la programmation système. Inventé au début des années 1970 avec UNIX, C est devenu un des langages les plus utilisés. De nombreux langages plus modernes se sont inspirés de sa syntaxe. Il privilégie la performance sur la simplicité de la syntaxe. [En savoir plus]
Le C++ est un langage de programmation impératif. Inventé au début des années 1980, il apporte de nouveaux concepts au langage C (les objets, la généricité), le modernise et lui ajoute de nombreuses bibliothèques. C++ est devenu l'un des langages les plus utilisés. Sa performance et sa richesse en font le langage de prédilection pour les concours. [En savoir plus]
Pascal est un langage de programmation impératif inventé dans les années 1970 dans un but d'enseignement. Quoiqu'encore utilisé à cette fin, l'absence de bibliothèque standard en limite son utilisation malgré une grande efficacité. Sa syntaxe a été reprise par d'autres langages plus modernes avec plus ou moins de succès. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
OCaml est un langage de programmation fonctionnel inventé au milieu des années 1990. Il permet aussi une programmation impérative ou objet. Il permet d'écrire des programmes courts et faciles à vérifier et est ainsi utilisé pour certains systèmes embarqués très sensibles comme ceux des avions. Il est utilisé dans l'enseignement en classes préparatoires aux grandes écoles. [En savoir plus]


Remarque : Les cours pour ce langage ne sont disponibles que jusqu'au chapitre 4, « Lecture de l'entrée ». Les corrections sont toutefois toujours fournies.
Java est un langage de programmation impératif et orienté objet. Inventé au début des années 1990, il reprend en grande partie la syntaxe du langage C++ tout en la simplifiant, au prix d'une performance un peu moins bonne. S'exécutant dans une machine virtuelle, il assure une grande portabilité et ses très nombreuses bibliothèques en font un langage très utilisé. On lui reproche toutefois la « verbosité » de son code. [En savoir plus]


Remarque : Pour un débutant souhaitant apprendre Java, nous conseillons fortement de commencer par JavaScool, plus facile à apprendre, bien que fortement similaire.
Java's Cool (alias JavaScool) est conçu spécifiquement pour l'apprentissage des bases de la programmation. Il reprend en grande partie la syntaxe de Java sur laquelle il s'appuie, mais la simplifie pour un apprentissage plus aisé. La plateforme JavaScool est accompagnée d'un ensemble d'activités diverses de découverte de la programmation. [En savoir plus]
Python est un langage de programmation impératif inventé à la fin des années 1980. Il permet une programmation orientée objet et admet une syntaxe concise et claire qui en font un langage très bien adapté aux débutants. Étant un langage interprété, il n'est cependant pas aussi performant que d'autres langages. [En savoir plus]
Le siècle a été tranquille sur Olympe et les dieux s'ennuient. Pas de guerres à influencer, pas d'affaires à régler --- les humains s'entendent plutôt bien les uns avec les autres. Vous décidez donc d'organiser une course de chars.

Comme vous êtes des dieux, ce ne sont bien sûr pas des chars ordinaires. Vous faites la course à travers les cieux d'étoile en étoile. Votre objectif est d'être le premier à atteindre la plantation d'oliviers d'Alpha du Centaure et Héra a promis au gagnant une bouteille du fameux Doux Nectar d'Elysium. Pour un prix aussi prestigieux, vous êtes déterminé à sortir victorieux.

Mais même pour les dieux, il y a des règles. Vous ne pouvez pas voler directement vers Alpha du Centaure, sinon Zeus (qui a le char le plus rapide) serait nettement le gagnant. Chacun d'entre-vous dispose d'une carte de la galaxie vous indiquant entre quelles étoiles vous pouvez voler.

Pour rendre la course encore plus passionnante, certaines étoiles sont reliées par des trous de ver. Traverser un trou de ver vous permet en fait de remonter dans le temps. Héra a donné des instructions strictes à Zeus et celui-ci ne peut utiliser les trous de ver (étant à la tête de tous les dieux, il se doit d'avoir un handicap), mais le reste d'entre-vous est autorisé à les utiliser aussi souvent que vous le souhaitez.

Supposez que la course commence au temps 0. Si vous entrez dans un trou de ver au temps t minutes, alors vous atteignez l'autre extrémité au temps t/2 minutes. Comme les dieux n'ont toujours pas inventé les fractions, si t est un nombre impair, alors vous devez l'arrondir en dessous. Par exemple, si vous entrez dans un trou de ver au temps 10 minutes, vous en sortirez au temps 5 et si vous entrez dans un trou de ver au temps 15 minutes, vous en sortirez au temps 7.

Votre objectif est de définir votre parcours à travers les cieux pour qu'il vous permette d'arriver à la plantation d'oliviers d'Alpha du Centaure le plus tôt possible. Notez que vous pouvez passer par Alpha du Centaure plus d'une fois, i.e., vous êtes autorisé à passer par Alpha du Centaure à un temps donné, utiliser un ou plusieurs trous de ver et y retourner plus tôt dans le temps pour gagner la course.

Limites de temps et de mémoire (Python)

  • Temps : 1 s sur une machine à 1 GHz.
  • Mémoire : 32 000 ko.

Contraintes

  • 1 <= N <= 100, où N est le nombre d'étoiles.

Entrée

Votre programme doit lire directement sur l'entrée standard. La première ligne de l'entrée contiendra un entier N représentant le nombre d'étoiles. Ces étoiles seront numérotées 1,2, ...,N.

La deuxième ligne de l'entrée contiendra deux entiers S et F, séparés par un espace, où S est l'étoile à laquelle vous commencez la course et F est l'étoile à laquelle vous la terminez (i.e., Alpha Du Centaure). On vous garantit que 1 <= S,F <= N.

La troisième ligne de l'entrée contiendra un seul entier P, représentant le nombre de chemins ordinaires que vous êtes autorisés à prendre pour aller d'une étoile à l'autre. Chacune des P lignes suivantes décrit un chemin et contient trois entiers A, B et T séparés par des espaces, qui signifient que vous êtes autorisé à aller de l'étoile A à l'étoile B et que le voyage vous prendra exactement T minutes. On vous garantit que 1 <= A,B <= N, que A <> B et que 1 <= T <= 1000.

La ligne suivante de l'entrée contiendra un entier W représentant le nombre de trous de ver. Chacune des W lignes suivantes décrit un trou de ver et contient deux entiers A, B séparés par un espace, indiquant que le trou de ver vous transporte de l'étoile A à l'étoile B (et vous fait remonter dans le temps). On vous garantit que 1 <= A,B <= N et A <> B.

Notez que tous les chemins et trous de ver sont en sens unique. C'est à dire que si l'entrée contient un chemin ou trou de ver allant de l'étoile A à l'étoile B, vous ne pouvez pas utiliser ce chemin ou trou de ver pour aller de l'étoile B à l'étoile A (bien sûr, un autre chemin ou trou de ver allant de B à A peut apparaître autre-part dans l'entrée). On vous garantit que deux chemins ou trous de ver ne vous amèneront jamais de la même étoile A à la même étoile B et qu'il est toujours possible d'atteindre Alpha du Centaure.

Sortie

Votre programme doit écrire directement sur la sortie standard. Votre sortie doit consister en un seul entier décrivant le temps le plus petit auquel vous pouvez arriver sur Alpha du Centaure.

Exemple

entrée :

6
1 6
7
1 2 10
1 4 8
2 3 5
3 6 10
4 3 6
4 5 7
5 6 12
1
5 2

sortie :

22

Commentaires

L'exemple d'entrée représente la carte illustrée ci-dessus. Les chemins normaux sont marqués comme des lignes continues et les trous de ver sont indiqués par des pointillés. Le départ de la course se fait sur l'étoile 1, sur la gauche et l'arrivée sur l'étoile 6, sur la droite.

La route la plus courte utilisant des chemins ordinaires du départ à l'arrivée est 1 -> 4 -> 3 -> 6, ce qui prend un temps total de 8+6+10=24 minutes. Cependant si l'on utilise le trou de ver, on peut atteindre l'arrivée plus tôt.

Si l'on voyage le long du chemin ordinaire 1 -> 4 -> 5, on atteint l'étoile 5 au temps 15. Emprunter le trou de ver 5 -> 2 nous ramène au temps 7 et l'on peut ensuite terminer le voyage par le chemin 2 -> 3 -> 6 pour atteindre l'arrivée au temps final de 7+5+10=22.

Vous devez être connecté pour résoudre cet exercice.

Vous devez être connecté(e) pour résoudre ce problème.

L'inscription ne prendra qu'une minute et vous pourrez alors résoudre les exercices puis faire valider automatiquement vos solutions.

Une fois identifié(e), vous pourrez demander sur cette page des conseils pour résoudre le sujet ou demander de l'aide sur le forum d'entraide.

Lorsque vous serez connecté(e), vous pourrez voir vos actions ici.

Une correction détaillée sera disponible lorsque vous aurez résolu le sujet.

Correction en cours de chargement…