Le Juste Chemin – Qualification 2025

Niveau 4 ⋅ Validation weight: 15%

Énoncé

Joseph Nageant est tout proche du but, il ne reste plus qu'à obtenir quelques informations sur l'accès à la forteresse pour pouvoir enfin y aller.

Pour cela, il compte dérober certains documents à plusieurs endroits dans la ville. Seulement, voilà que notre ami arrive à court d'oxygène…

La ville sous-marine est composée de $N$ maisons, numérotées de $1$ à $N$.

Chaque maison possède un score associé, qui est l'entier correspondant dans le tableau scores. Ce score correspond à la valeur des informations pouvant être dérobées dans cette maison.

Joseph Nageant dispose de $K$ minutes pour récupérer les informations qu'il recherche avant la prochaine patrouille des gardes. Il peut se déplacer d'une maison $A$ à une maison $B$ (ou inversement) en une minute si les deux maisons sont directement reliées par une route. La liste des $M$ routes est donnée par le tableau routes.

Joseph Nageant va bientôt tomber à court d'oxygène. Fort heureusement, il sait aussi qu'une unique maison, la maison $1$, stocke des réserves d'oxygène, ce qui lui permet de remplir ses réserves.

On dit alors qu'un chemin $M_0, M_1, \dots, M_i$ est juste si:

  • La longueur du chemin (c'est-à-dire, $i$) est inférieure ou égale à $K$,
  • La maison $1$ est présente dans le chemin, c'est à dire $M_j = 1$ pour au moins un $j$.

On dit également qu'une paire de maisons $(A, B)$ est juste s'il existe au moins un chemin juste reliant ces deux maisons. Le score de cette paire est alors le produit des scores des maisons $A$ et $B$.

Il vous est demandé de déterminer toutes les paires de maisons justes, et d'en afficher la somme de leur score. Comme le résultat peut devenir très grand, affichez cette somme modulo $1\,000\,000\,007$.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : N, le nombre de maisons.
  • Sur la ligne suivante, un entier : M, le nombre de routes.
  • Sur la ligne suivante, un entier : K, le temps restant à Joseph, soit la longueur maximale d'un chemin juste.
  • Sur la ligne suivante, une liste de N entiers séparés par des espaces : scores, le score associé à chaque maison.
  • Sur les lignes suivantes, une liste de M éléments : routes, la liste des routes.
    • Une ligne par élément de la liste : séparés par des espaces, un entier A (la première maison), et un entier B (la seconde maison).

Sortie

Afficher, sur une ligne, la somme des scores des paires de maisons justes, modulo $1\,000\,000\,007$.

Contraintes

  • $2 \le N \le 100$
  • $1 \le M \le 1\,000$
  • $1 \le K \le N$
  • $0 \le \mathtt{scores}_i \le 1\,000\,000\,006$
  • $1 \le A_i, B_i \le N$
  • Il n'y a pas de route reliant une maison à elle-même, et toutes les routes sont distinctes.

Contraintes de performance

  • $2 \le N \le 200\,000$
  • $1 \le M \le 200\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
4
5
2
2 2 3 4
1 2
1 3
2 3
2 4
3 4
Exemple de sortie
65
Commentaire

Voici à quoi ressemble les routes entre les maisons :

graphe

Par exemple, les paires (2, 3) et (3, 2) sont des paires justes, car il existe un chemin de longueur 2 entre la maison 2 et la maison 3 qui passe par la maison 1 (source d'oxygène).

En vert est représenté le score associé à chaque maison.

Voici la liste des paires de maisons justes, avec pour chaque paire un exemple de chemin juste associé, et le score de la paire.

      paire            chemin            score      
(1, 1) (1) $2 \times 2 = 4$
(1, 2) (1, 2) $2 \times 2 = 4$
(1, 3) (1, 3) $2 \times 3 = 6$
(1, 4) (1, 2, 4) $2 \times 4 = 8$
(2, 1) (2, 1) $2 \times 2 = 4$
(2, 2) (2, 1, 2) $2 \times 2 = 4$
(2, 3) (2, 1, 3) $2 \times 3 = 6$
(3, 1) (3, 1) $3 \times 2 = 6$
(3, 2) (3, 1, 2) $3 \times 2 = 6$
(3, 3) (3, 1, 3) $3 \times 3 = 9$
(4, 1) (4, 2, 1) $4 \times 2 = 8$

Cela se cumule en un total de 65.

Au contraire, la paire (4, 3) n'est pas une paire juste, car il est impossible d'aller de la maison 4 à la maison 3 en passant par la maison 1 en deux routes ou moins.

Exemple d'entrée
5
4
3
1000000 0 0 1000000 1000000
4 2
2 1
1 3
3 5
Exemple de sortie
999965007
Commentaire

graphe

Dans cette configuration, quasiment toutes les paires de maisons sont justes, à l'exception de:

  • (4, 4), (4, 5), (5, 4), (5, 5),

qui nécessitent un chemin d'une longueur de 4 au moins pour passer par la maison $1$.

Parmi les paires justes, cinq rapportent du score (les autres effectuent une multiplication par 0 dans le calcul du score):

  • (1, 1), (1, 4), (1, 5), (4, 1), (5, 1)

Chacune de ces paires rapportent $10^6 \times 10^6 = 10^{12}$ points, pour un total de $5 \times 10^{12}$ points.

Ramené modulo $1\,000\,000\,007$, il faut donc afficher $999\,965\,007$.