On se donne n villes indexées de 1 à n. Ces villes sont parfois reliées par une voie ferrovière directe, parfois pas. Ces données sont regroupées dans une matrice M indexée par deux entiers i et j tels que M(i,j) désigne la longueur (en km) de la voie ferrovière directe reliant la ville i à la ville j, 0 s'il n'y en a pas. Notez que cette matrice est symmétrique.
Un indicateur utilisé pour qualifier les performances de l'installation ferrée est la distance moyenne en voie ferrée pour rejoindre deux villes. Lorsque ces deux villes ne sont pas directement reliées, on considère la plus courte façon de les relier en passant par une ou plusieurs autres villes.
Votre objectif est de calculer la valeur de cet indicateur. Vous pourrez pour cela vous aider de l'algorithme de Roy-Warshall (parfois appelé Floyd-Warshall).
Entrée
L'entrée contient d'abord l'entier n sur une ligne, puis les n lignes de la matrice M, où les éléments sont séparés par des espaces.
On ne considérera jamais plus de 50 villes, et la distance d'une ville à une autre n'excédera pas 1000 km.
Sortie
La sortie contient l'indicateur défini dans l'énoncé, arrondi à l'entier le plus proche. On supposera que le réseau ferré est connexe, ce qui veut dire que l'on peut se rendre d'une ville à n'importe quelle autre par le réseau ferré.