Prologin
2024
Énoncé¶
En Grèce antique, les Jeux Olympiques sont source de conflit, chez les hommes comme chez les dieux. Zeus demande donc l'aide de Joseph pour mettre tout le monde d'accord. Il y a exactement le même nombre de dieux que d'athlètes et chaque dieu aimerait pouvoir retourner dans son temple avec un de ses champions préférés après les JO. La liste de préférence d'un dieu est déterminée par la quantité d'offrandes que chaque athlète lui aura donnée avant la compétition. Plus un athlète donne d'offrandes a un dieu, plus il est aimé de ce dieu. Cependant les athlètes aussi ont leur ordre de préférence : ils sont paresseux et ne veulent pas trop voyager pour se rendre au temple du dieu en question. Pour assigner un athlète à chaque dieu et éviter les convoitises, Zeus aimerait que cette assignation soit telle qu'il n'existe pas de dieux A et B ni d'athlètes X et Y tels que :
- X est assigné à A
- Y est assigné à B
- B a reçu plus d'offrandes de la part de X que de Y
- X est plus proche du temple de B que du temple de A
Si cette propriété n'est pas vérifiée, un athlète pourrait être tenté de se rendre dans un temple plus proche que celui assigné et le dieu en question aurait tout intérêt à accepter ce changement, ce qui créerait un scandale de plus sur l'Olympe.
Notez qu'il existe toujours une solution à ce problème.
La carte de Grèce est représentée par un graphe pondéré et non orienté. Les sommets du graphe sont les grandes villes grecques. Les arêtes du graphe sont les routes qui vont d'une ville à une autre, pondérées par la distance (toujours positive) entre les deux ville. On ne garantit pas que le graphe est planaire. On garantit cependant que le graphe est connexe (en un seul morceau). Les temples et les athlètes sont répartis sur les sommets du graphe mais rien n'empêche une même ville d'héberger plusieurs temples et/ou plusieurs athlètes.
Entrée¶
L’entrée contiendra :
- Sur la première ligne, un entier : $n$, le nombre de dieux/athlètes.
- Sur les lignes suivantes, une liste de $n$ éléments : offrandes, les
offrandes que reçoivent les dieux.
- Une ligne par élément de la liste : une liste de $n$ entiers séparés par des espaces.
- Sur la ligne suivante, un entier : $m$, le nombre de villes.
- Sur la ligne suivante, une liste de $n$ entiers séparés par des espaces : athletes, la position des athlètes dans le graphe.
- Sur la ligne suivante, une liste de $n$ entiers séparés par des espaces : temples, la position des temples dans le graphe.
- Sur la ligne suivante, un entier : $p$, le nombre de routes.
- Sur les lignes suivantes, une liste de $m$ éléments : routes, les
routes de la carte.
- Une ligne par élément de la liste : séparés par des espaces, un entier $u$ (première ville), un entier $v$ (deuxième ville), et un entier $d$ (distance entre les deux villes).
Sortie¶
Afficher $n$ entiers sur une seule ligne : le $i^\text{ème}$ entier est le numéro de l'athlète que vous voulez attribuer au dieu $i$.
Contraintes¶
- $1 \le m \le 1\,000$
- $1 \le n \le m \le p \le 10 \times m$
- les entiers représentant une quantité d'offrande tiennent sur un entier de 32 bits signé.
