|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1729. Склад
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
На некоторой территории имеется N деревень и M непересекающихся двухсторонних дорог, соединяющих некоторые пары деревень. Местный предприниматель решил открыть сеть магазинов, разместив по одному магазину в каждой деревне. Теперь ему нужно выбрать место для центрального склада, из которого товары будут развозиться по магазинам. Предприниматель хочет разместить склад так, чтобы расстояние от него до самого дальнего магазина было как можно меньше. Склад может находиться в одной из деревень или в любой точке дороги из одной деревни в другую. Определите, какое наименьшее расстояние до самого дальнего магазина получится при оптимальном размещении склада. Входные данные В первой строке входных данных записаны через пробел два числа N и M — количество деревень и количество дорог (1 ≤ N ≤ 100, 0 ≤ M ≤ 10000). Каждая из следующих M строк содержит описание очередной дороги — три числа Fi, Ti, Li, где Fi и Ti — номера деревень (1 ≤ Fi, Ti ≤ N), Li — длина дороги (1 ≤ Li ≤ 10000). Некоторые пары деревень могут быть соединены более чем одной дорогой. Гарантируется, что из любой деревни можно добраться до любой другой. Выходные данные Выведите одно вещественное число — наименьшее расстояние от склада до самой дальней деревни. Ответ нужно вывести с точностью не менее четырёх знаков после десятичной точки. Пример Входные данные 3 4 Выходные данные 3.5000 Примечание В примере склад наиболее выгодно разместить на дороге между деревнями 2 и 3 на расстоянии 0.5 километра от деревни 2.
|
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Межвузовские олимпиады / | XX межвузовская олимпиада - 2017 / |
| 1728. I - Цепные дроби | 1729. |
| время генерации 0.078 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |