Restauration rapide – Qualification 2018

Niveau 4

Énoncé

Pour atteindre une clientèle plus importante, Joseph Marchand (de crêpes) envisage d'offrir un service de livraison sur la plage. Avant de lancer son nouveau modèle, il fait appel à vous pour évaluer la rentabilité de l'opération.

Joseph a tracé dans le sable des routes qui relient les clients. Pour gagner du temps, il a tracé le minimum possible de routes (mais il s'est tout de même assuré de relier tous les clients à son réseau de distribution).

En empruntant ses routes (dans un sens ou dans l'autre), Joseph se demande quelle est la distance moyenne à parcourir pour aller d'un client à un autre.

Entrée

L'entrée comprendra plusieurs lignes :

  • La première ligne contiendra un entier $M$, le nombre de routes tracées dans le sable.
  • Les M lignes suivantes contiennent chacune 3 entiers $x$, $y$ et $l$, signifiant que les clients $x$ et $y$ sont directement reliés par une route de longueur $l$.

Sortie

Vous afficherez un entier, la longueur moyenne (arrondie à l'entier inférieur) qu'il faut parcourir pour rejoindre deux clients.

Contraintes

  • $1 \le M \le 1\ 000$
  • $0 \le x, y \le M$
  • $1 \le l \le 100$

Contraintes de performance

  • $1 \le M \le 50\ 000$

Contraintes d'exécution

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

Exemples d'entrée/sortie

Exemple d'entrée
2
0 1 1
0 2 2
Exemple de sortie
2
Commentaire

La distance entre les clients 0 et 1 est 1. La distance entre les clients 0 et 2 est 2. La distance entre les clients 1 et 2 est 3 (en passant par le client 0).

La moyenne est donc de 2.

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

La distance entre les clients 0 et 1 est 1. La distance entre les clients 0 et 2 est 2. La distance entre les clients 0 et 3 est 5. La distance entre les clients 1 et 2 est 3. La distance entre les clients 1 et 3 est 4. La distance entre les clients 2 et 3 est 7.

La moyenne est donc de 11/3 (arrondie à 3).