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]
Vous et votre meilleur ami participez à un grand jeu de piste dans la forêt. Le but du jeu est de résoudre E énigmes (numérotées de 1 à E) posées par des organisateurs situés en différents lieux de la forêt, dont on vous fournit les coordonnées GPS. Atteindre les positions des énigmes n'est pas un problème, car vous disposez tous deux d'un ordinateur de poche dernier cri, avec géolocalisation, vous permettant à tout moment de visualiser votre position sur une carte détaillée de la forêt, ainsi que les positions de toutes les énigmes.

Toute la difficulté du jeu va donc consister à résoudre les énigmes. Aucun de vous deux n'est très doué pour le genre d'énigmes proposées dans ce jeu. La première énigme est toujours facile à résoudre, mais les autres sont quasiment introuvables sans un indice. Heureusement, une fois que vous avez résolu une énigme donnée, l'organisateur qui vous l'a posée vous donne un gros indice qui vous permet de résoudre facilement l'énigme suivante (par ordre de leur numéro).

Pour éviter de perdre du temps à chercher à résoudre les énigmes sans indices, vous décidez donc de les résoudre dans l'ordre de leur numéro. Les énigmes sont cependant placées de manière assez aléatoire dans la forêt, et les parcourir dans l'ordre demande de nombreux allers-retours.

Pour éviter de perdre trop de temps, vous et votre ami décidez de vous séparer, et de vous répartir les énigmes. Vous pouvez par exemple décider de résoudre toutes les énigmes paires, tandis que votre ami résoudra les énigmes impaires. Ainsi, dès que votre ami aura résolu l'énigme numéro 1, et obtenu l'indice pour l'énigme numéro 2, il vous l'enverra par mail via son ordinateur de poche, et vous pourrez alors résoudre cette énigme dès que vous aurez atteint sa position.

Vous décidez d'écrire un petit programme pour déterminer, à partir de la description de la carte et des positions des différentes énigmes, la meilleure répartition possible des énigmes entre vous et votre ami, c'est à dire celle qui permet de résoudre l'ensemble des énigmes en un minimum de temps.

Vous partez tous les deux de la position de l'énigme 1, et vous pouvez vous déplacer dans l'ensemble du graphe sans autre contrainte que le temps nécessaire pour parcourir chaque chemin. Vous pouvez traverser des énigmes sans les résoudre tout de suite, et pouvez également rester attendre sur une énigme en attendant de recevoir un indice.

Le jeu s'arrête lorsque vous résolvez la dernière énigme. On considèrera qu'une fois que vous êtes à la position où se trouve une énigme, et que vous ou votre ami avez résolu l'énigme précédente et obtenu l'indice, résoudre l'énigme suivante ne prend aucun temps. Seule l'énigme 1 peut être résolue sans indice.

On vous garantit qu'il est toujours possible de résoudre toutes les énigmes.

Limites de temps et de mémoire (Python)

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

Contraintes

  • 1 <= E <= 30, où E est le nombre d'énigmes.
  • 1 <= C <= 450, où C est le nombre de chemins reliant chacun les emplacements de deux énigmes.
  • 1 <= L <= 20, où L est le nombre de minutes pour parcourir un chemin.

Dans 30% des tests, on a E <= 15.

Dans 60% des tests (qui incluent les 30% précédents), on a C <= 50.

Entrée

La première ligne de l'entrée contient deux entiers séparés par un espace : le nombre E d'énigmes, et le nombre C de chemins à double sens reliant ces énigmes. Deux énigmes ne peuvent être reliés que par un seul chemin.

Chacune des E lignes suivantes décrit un chemin, sous la forme de 3 entiers séparés par des espaces : les numéros des lieux reliés par le chemin, puis le temps nécessaire en minutes pour le parcourir.

Les chemins sont donnés dans un ordre quelconque.

Sortie

Vous devez afficher un entier sur la sortie : le nombre minimal de minutes nécessaire pour résoudre toutes les énigmes dans l'ordre, en les répartissant au mieux entre vous et votre ami.

Exemple

entrée :

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

sortie :

15

Commentaires

L'entrée correspond au dessin fourni dans la description du sujet.

Voici le parcours le plus rapide pour vous (P1) et votre ami (P2).

Détail du déroulement :

TempsEvénement
0P1 résout l'énigme 1 et part vers l'énigme 2.
P2 part également de l'énigme 1, et se dirige vers l'énigme 3.
3P2 arrive à l'énigme 3 mais ne la résout pas et repart aussitôt vers l'énigme 7.
4P1 arrive à l'énigme 2 et la résout. Il obtient l'indice pour l'énigme 3 vers laquelle il se dirige.
6P2 arrive à l'énigme 7 et repart aussitôt vers l'énigme 4.
7P1 arrive à l'énigme 3, la résout, obtient l'indice de l'énigme 4 et le transmet à P2, puis part vers l'énigme 7.
10P1 arrive à l'énigme 7 et repart aussitôt vers l'énigme 5.
11P2 arrive à l'énigme 4 et la résout, puis envoie l'indice de l'énigme 5 à P1, et part vers l'énigme 6.
12P1 arrive à l'énigme 5, la résout et envoie l'indice de l'énigme 6 à P2, puis repart vers l'énigme 7.
14P1 arrive à l'énigme 7 et attend l'indice.
15P2 arrive à l'énigme 6, la résout et envoie l'indice de l'énigme 7 à P1.
P1 résout l'énigme 7.
Le jeu de piste est terminé.
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 sera mise en ligne après la fin de l'épreuve.