Кратчайший маршрут с выбором
Во входных данных содержится описание ациклического ориентированного взвешенного графа. Каждая строка задаёт одно ребро: в ней записаны номера вершин и и вес ребра, ведущего из вершины в вершину . Любые две вершины соединены не более чем одним ребром.
Найдите кратчайший путь из вершины с номером в вершину с номером и определите количество рёбер в нём. Если кратчайших путей несколько, выберите тот из них, в котором рёбер меньше. Под длиной пути понимается сумма весов рёбер, составляющих путь. Существование хотя бы одного такого пути гарантируется.
Входные данные
Входные данные содержат не более строк; читать их нужно до конца ввода. В каждой строке записаны два натуральных числа и и положительное вещественное число (, , ). Числа в строке разделены произвольным ненулевым количеством пробелов и (или) табуляций.
Вершины графа могут быть пронумерованы не подряд, а ребро может вести в вершину с меньшим номером. Вес записан ровно с одной цифрой после десятичной точки.
Выходные данные
Выведите одно целое число — количество рёбер в найденном пути.
Примеры
11 53 1.2 53 29 1.3 29 97 1.4 11 97 5.9 11 67 1.7 67 97 2.2
2
11 53 0.2 53 97 0.4 11 29 0.1 29 67 0.2 67 97 0.3
2
Примечание
В первом примере пути 11, 53, 29, 97 и 11, 67, 97 имеют одинаковую минимальную длину 3.9. В первом три ребра, во втором два, поэтому ответ — 2. Прямое ребро веса 5.9 не подходит по основному критерию.
Во втором примере оба пути имеют длину 0.6: . Выбирается путь из двух рёбер. Сравнивать нужно точные суммы весов, а не их целые части.