La meilleure ville – Qualification 2019

Niveau 4

Énoncé

Joseph Marchand est arrivé à Busland. C'est un pays où la majorité des déplacements entre les différentes villes se font par bus. Heureusement, dans ce pays, les bus sont très organisés : dans chaque ville on attend toujours un bus un temps fixé avant qu'il arrive, le temps d'attente dépend de la ville. Les routes aussi sont très bien organisées : il n'y a jamais aucun bouchon. On met toujours le même temps pour aller d'une ville à l'autre, ce temps dépend de la distance entre les deux villes.

Les routes entre les villes sont toujours à sens unique, en conséquence, avoir un bus direct de la ville A à la ville B ne veut pas dire qu'il y aura un bus direct de B à A. On ne prendra pas non plus nécessairement le même temps pour aller de A à B que de B à A.

Pour éviter d'encombrer le centre ville avec des voyageurs qui ne font que transiter, certaines villes ont mis en place des gares routières. Ces gares routières ont un avantage, les bus en partent en continu, il n'y a donc aucune attente au départ des gares routières.

Depuis la gare routière d'une ville A on peut atteindre les mêmes destinations que depuis la ville A (et les temps de transit sont les mêmes), en revanche, il est impossible de se rendre au centre ville de la ville A depuis la gare routière de la ville A. Pour arriver dans la gare routière d'une ville A il faut prendre un bus spécial à partir d'une autre ville, ce bus aura son propre temps de trajet.

Joseph veut savoir quelles sont les villes les plus interconnectées à Busland, et pour cela il a trouvé un moyen simple : il associe à chaque ville A un score. Ce score, c'est la moyenne prise sur chaque ville B accessible depuis A, du temps minimal qu'il mettra pour aller du centre ville de A au centre ville de B.

Votre rôle est d'aider Joseph Marchand à calculer les scores de chaques villes de Busland.

Entrée

Sur la première ligne trois entiers :

  • $n$, le nombre de villes ;
  • $m$, le nombre de lignes de bus joignant les villes ;
  • $g$, le nombre de lignes de bus à directions de gares routières.

Sur les $n$ prochaines lignes, le temps d'attente du bus pour la ville numéro $i$ (on commence à $i = 1$).

Puis, $m$ lignes de la forme : $a$ $b$ $t$ indiquant qu'il faut $t$ temps pour aller de la ville $a$ vers la ville $b$.

Enfin, $g$ lignes de la forme : $a$ $b$ $t'$ correspondant au temps $t'$ requis pour aller de la ville $a$ à la gare routière de la ville $b$.

Sortie

Les scores des villes, dans l'ordre de leurs numéros, un par ligne.

Si une ville ne permet d'atteindre aucune autre, son score est de -1.

Le score de chaque ville (si différent de -1), arrondi à l'entier inférieur.

Contraintes

  • $1 \le n \le 150$
  • $0 \le m \le 20 000$
  • $0 \le g \le 20 000$
  • $0 \le temps \le 1000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
3 3 0
3
10
5
1 2 4
2 3 5
1 3 2
Exemple de sortie
6
15
-1
Commentaire

Dans cet exemple il n'y a aucune route permettant d'accéder aux gares routières.

  • depuis la ville 1, on peut accéder aux deux autres villes, le plus court chemin est de prendre la ligne directe à chaque fois.
  • depuis la ville 2, on ne peut accéder qu'à la ville 3, il faut attendre son bus 10 minutes puis attendre pendant les 5 minutes de trajet.
  • depuis la ville 3, on ne peut accéder à aucune ville.
Exemple d'entrée
3 4 1
5
5
10
1 2 2
2 1 20
2 3 1
3 1 5
2 3 5
Exemple de sortie
10
10
18
Commentaire

NB: La ligne rouge est une ligne menant à une gare routière, les lignes bleues sont des lignes de bus classiques.

Ici, par exemple, pour aller de la ville 2 à la ville 1, on va aller à la gare routière de la ville 3, puis prendre le bus jusqu'à la ville 1, sans attendre.