|
Remote Training on Programming
|
||||||||||
|
|
|||||||||||
| Hello, Guest! Please login or register. |
1729. Store
|
| View Problem Statistics | Submit | Problem added 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.
|
| View Problem Statistics | Submit | Problem discussion | Author/source: |
| Problems from Contests and Camps / | Vologda Students Contests / | XX Interuni Olympiad - 2017 / |
| 1728. I - Chain Fractions | 1729. |
| time generating 0.109 sec. |
| © Copyright VSU, AVT, Nosov D.A., Andrianov I.A. |