Prologin
2026
Énoncé¶
Arrivé au point de rencontre indiqué par la lettre, il rencontre alors enfin son auteur. Quelle surprise ! Il s'agit du dirigeant de la ville lui-même, Joseph Martial !
Le dirigeant explique alors qu'il est lui aussi au courant des manigances qui se produisent dans la ville, et compte bien nous aider à les faire cesser. Notre objectif est maintenant de trouver la salle de contrôle où les dispositifs doivent sûrement se trouver.
Le dirigeant suspecte deux gardes de la ville, Joseph Traque et Joseph Matraque, d'être affiliés à ce complot. Après quelques investigations, vous avez pu obtenir l'information que les deux gardes vont se retrouver aujourd'hui pour s'échanger un colis confidentiel. Votre objectif va donc être de les intercepter avant que l'échange de colis n'ait lieu.
La ville est représentée par un graphe pondéré non orienté, dont les arêtes symbolisent les rues, les poids symbolisent le temps nécessaire pour traverser la rue, et les sommets symbolisent les intersections entre les différentes rues.
Les deux gardes, Traque et Matraque, sont situés sur deux sommets du graphe, et tentent de se rejoindre afin d'échanger un colis. Pour ce faire, ils suivent tous deux un chemin défini en entrée.
Joseph a comme mission d'empêcher cet échange d'avoir lieu. Pour cela, il doit se trouver sur un sommet au moment ou l'un des deux gardes le traverse. Cependant, si Joseph arrive après que les deux gardes ont échangé leur colis, il sera alors trop tard pour les intercepter. Ainsi, si les trois personnes se rencontrent en même temps sur un sommet, l'interception a tout de même lieu.
La position initiale de Joseph sera une intersection donnée explicitement en entrée, tandis que Traque et Matraque commenceront respectivement au début et à la fin de leur chemin indiqué. Les déplacements de Joseph, Traque et Matraque s'effectuent de sommet en sommet, en "temps réel".
Aidez Joseph à déterminer le temps nécessaire au minimum pour intercepter l'un
des deux gardes. Si l'interception est impossible à temps, affichez -1.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : N, nombre d'intersections dans la ville.
- Sur la ligne suivante, un entier : M, nombre de rues.
- Sur les lignes suivantes, une liste de M éléments : rues, liste des
rues.
- Une ligne par élément de la liste : séparés par des espaces, un entier intersection 1 (1ère intersection), un entier intersection 2 (2ème intersection), et un entier temps (temps nécessaire pour traverser la rue).
- Sur la ligne suivante, un entier : longueur chemin, nombre d'intersections dans le chemin emprunté par Traque et Matraque.
- Sur la ligne suivante, une liste de longueur chemin entiers séparés par des espaces : chemin, liste des intersections représentant le chemin emprunté par Traque et Matraque.
- Sur la ligne suivante, un entier : joseph, position de Joseph.
Sortie¶
Afficher, sur une ligne, le temps minimal nécessaire à Joseph pour intercepter
Traque ou Matraque. S'il est impossible pour Joseph d'intercepter Traque ou
Matraque à temps, afficher -1.
Contraintes¶
- $3 \le N \le 15$
- $2 \le M \le 20$
- $1 \le \mathtt{longueur chemin} \le 15$
- $1 \le \mathtt{chemin}_i \le N$
- $1 \le \mathtt{joseph} \le N$
- $1 \le \mathtt{intersection 1} \le N$
- $1 \le \mathtt{intersection 2} \le N$
- $1 \le \mathtt{temps} \le 15$
- On vous garantit que le chemin de Traque et Matraque est un chemin simple, donc que tous les sommets de ce chemin sont distincts.
Contraintes de performance¶
- $2 \le N \le 100\,000$
- $2 \le M \le 200\,000$
- $1 \le \mathtt{longueur chemin} \le 100\,000$
- $1 \le \mathtt{temps} \le 100\,000$
