Məsələlər
Граф 1, 1/2, 1/3, 1/4
Граф 1, 1/2, 1/3, 1/4
Дан связный, взвешенный неориентированный граф, ребра которого имеют веса 1, 1/2, 1/3, 1/4. Найдите кратчайший путь от вершины 1 до всех остальных.
Входные данные
В первой строке записаны два натуральных числа n и m (1 ≤ n ≤ 105
, 1 ≤ m ≤ 8 *105
) - количество вершин и ребер графа соответственно. Далее записаны ребра на отдельных строках. Ребра задаются тремя натуральными числами: u, v и w (1 ≤ u, v ≤ n, u ≤ v, 1 ≤ w ≤ 4), которые обозначают наличие ребра из u в v веса 1/w.
Выходные данные
Для каждой вершины от 2 до n выведите одно число - длину кратчайшего пути от вершины 1 до нее, с точностью не менее 8 знаков после запятой.
Giriş verilənləri #1
4 4 1 2 1 2 3 2 3 4 4 4 1 3
Çıxış verilənləri #1
1.00000000 0.58333333 0.33333333