On se donne n villes indexées de 1 à n. Ces villes sont parfois reliées par une voie ferroviaire 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 ferroviaire directe reliant la ville i à la ville j, 0 s'il n'y en a pas. Notez que cette matrice est symé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).

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.

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é.

Squelettes de codes :

(* Ce fichier contient tout ce qu'il faut pour lire les donnees en entree, les 
mettre dans des variables, et afficher votre resultat final en sortie. *)

(* fonction pour separer les elements en entree 
Il n'est pas necessaire de comprendre cette fonction pour utiliser le programme !*)
let split_spaces chaine =
  let res = ref [] in
  let temp = ref "" in
  for i = 0 to String.length chaine - 1 do
    if chaine.[i]=' '
    then 
      begin
        res := !res @ [!temp];
        temp := "";
      end
    else
      temp := !temp ^ (String.sub chaine i 1);
  done;
  res := !res @ [!temp];
  !res;;

(* On lit le nombre de villes n *)
let n = int_of_string (input_line stdin)

(* On lit la liste des distances de ville à ville *)
let distances = Array.init n (fun _ -> Array.map int_of_string (Array.of_list (split_spaces (input_line stdin))))

(* fonction pour afficher votre solution *)
let affiche_solution i =
  print_int i;
  print_newline();;

(* Mettez apres ceci le corps de votre programme *)
(* N'oubliez pas de terminer par un appel a affiche_solution !*)

(* Debut de votre programme *)

(* Fin de votre programme *)