Задача №3342. Среднее расстояние (C)
Вам дано описание дорожной сети страны. Ваша задача – найти среднюю длину кратчайшего пути между двумя городами. Средней длиной называется отношение суммы по всем парам городов (\(a\), \(b\)) длин кратчайших путей \(l_{a,b}\) из города \(a\) в город \(b\) к числу таких пар. Здесь \(a\) и \(b\) – различные натуральные числа в диапазоне от 1 до \(N\), где \(N\) – общее число городов в стране. Следует учитывать только такие пары городов, между которыми есть кратчайший путь.
Сеть дорог задана во входном файле следующим образом: первая строка содержит числа \(N\) и \(K\) (\(1 \leq N \leq 100, 1 \leq K \leq N(N-1)\)), где \(К\) – количество дорог. Каждая из следующих \(K\) строк содержит описание дороги с односторонним движением – три целых числа \(a_i\), \(b_i\) и \(l_i\) (\(1 \leq a_i,b_i \leq N\), \(1 \leq l_i \leq 1000\)). Это означает, что имеется дорога длины \(l_i\), которая ведет из города \(a_i\) в город \(b_i\).
Вы должны вывести в выходной файл единственное вещественное число – среднее расстояние между городами. Расстояние должно быть выведено с 6 знаками после десятичной точки.
6 4 1 2 7 3 4 8 4 5 1 4 3 100
25.000000