Prologin
2026
Énoncé¶
Pour préparer le retour des humains sur Terre, Joseph remet en état les axes principaux de la ville. Pour ce faire, il faut majoritairement déplacer des gravats et des structures effondrées. Les robots qui se chargent de ce travail doivent traverser des ponts, malheureusement peu utilisés et dégradés avec le temps.
Joseph veut remettre en état un lieu $A$ et peut déplacer les ressources inutiles dans un lieu $B$.
Pour cela, les robots[1] peuvent utiliser le réseau routier de la ville. Cependant, chaque route est plus ou moins dégradée, si bien qu'une route $i$ ne peut faire passer que $\text{capacite}$ ressources. Les routes sont bidirectionnelles, en ligne droite et ne se croisent pas. Votre tâche est d'indiquer combien de ressources peuvent être transportées au maximum du lieu $A$ au lieu $B$ en sécurité.
[1] Dont RobobLeBricoleur, RobobMarley, RobobDylan, RobobLÉponge
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : N, le nombre de lieux.
- Sur la ligne suivante, un entier : M, le nombre de routes.
- Sur les lignes suivantes, une liste de N éléments : lieux, la position
de chaque lieu.
- Une ligne par élément de la liste : séparés par des espaces, un entier x (la coordonnée X), et un entier y (la coordonnée Y).
- Sur les lignes suivantes, une liste de M éléments : routes, la
description de chaque route.
- Une ligne par élément de la liste : séparés par des espaces, un entier u (le premier lieu), un entier v (le second lieu), et un entier capacite (seuil de sécurité de la route).
- Sur la ligne suivante, un entier : A, indice du lieu de départ.
- Sur la ligne suivante, un entier : B, indice du lieu d’arrivée.
Sortie¶
Afficher, sur une ligne, le nombre maximal de ressources pouvant être transportées jusqu'au lieu B en toute sécurité depuis le lieu A en utilisant uniquement le réseau routier.
Contraintes¶
- $4 \le N \le 300$
- $6 \le M \le 900$
- $1 \le A, B \le N$
- $-10^{9} \le x \le 10^{9}$
- $-10^{9} \le y \le 10^{9}$
- $1 \le u, v \le N$
- $u \ne v$
- $1 \le capacite \le 10^{9}$
- Chaque lieu est relié directement à au moins 3 autres lieux par une route.
Contraintes de performance¶
- $4 \le N \le 100\,000$
- $6 \le M \le 300\,000$
