La meilleure ville – Qualification 2019

Level 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$

Runtime constraints

Maximum memory usage
1000 kilobytes
Maximum execution time
1000 milliseconds

Input/output samples

Sample input
3 3 0
3
10
5
1 2 4
2 3 5
1 3 2
Sample output
6
15
-1
Note

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.
Sample input
3 4 1
5
5
10
1 2 2
2 1 20
2 3 1
3 1 5
2 3 5
Sample output
10
10
18
Note

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.

Submit your solution

You have to register or log in to be able to submit your solution.