Олимпиадный тренинг

Задача . 27284


Задача

Темы:

Вам дано описание дорожной сети страны в виде весовой матрицы. Ваша задача – найти среднюю длину пути от первого пункта пути до всех остальных. Средней длиной называется отношение суммы по всем парам городов (ab) длин кратчайших путей la,b из города a в город b к числу таких пар. Здесь a и b – различные натуральные числа в диапазоне от 1 до N, где N – общее число городов в стране. Следует учитывать только такие пары городов, между которыми есть кратчайший путь.

Входные данные

Сеть дорог задана во входном файле следующим образом: первая строка содержит числа N и K (1<=N<=100,1<=K<=N(N−1)), где К  – количество дорог. Каждая из следующих K строк содержит описание дороги с односторонним движением – три целых числа aibi и li (1<=ai,bi<=N1<=li<=1000). Это означает, что имеется дорога длины li, которая ведет из города ai в город bi.

Выходные данные

Вы должны вывести в выходной файл единственное вещественное число – среднее расстояние между первым городом и всеми остальными. Расстояние должно быть выведено с 6 знаками после десятичной точки.



time 500 ms
memory 32 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
Комментарий учителя