Кратчайший маршрут с выбором

Время 2 с · память 256 МБ

Во входных данных содержится описание ациклического ориентированного взвешенного графа. Каждая строка задаёт одно ребро: в ней записаны номера вершин LL и MM и вес WW ребра, ведущего из вершины LL в вершину MM. Любые две вершины соединены не более чем одним ребром.

Найдите кратчайший путь из вершины с номером 1111 в вершину с номером 9797 и определите количество рёбер в нём. Если кратчайших путей несколько, выберите тот из них, в котором рёбер меньше. Под длиной пути понимается сумма весов рёбер, составляющих путь. Существование хотя бы одного такого пути гарантируется.

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

Входные данные содержат не более 200200 строк; читать их нужно до конца ввода. В каждой строке записаны два натуральных числа LL и MM и положительное вещественное число WW (L≤1000L \le 1000, M≤1000M \le 1000, W≤10 000W \le 10\,000). Числа в строке разделены произвольным ненулевым количеством пробелов и (или) табуляций.

Вершины графа могут быть пронумерованы не подряд, а ребро может вести в вершину с меньшим номером. Вес WW записан ровно с одной цифрой после десятичной точки.

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

Выведите одно целое число — количество рёбер в найденном пути.

Примеры

Ввод 1
11 53 1.2
53 29 1.3
29 97 1.4
11 97 5.9
11 67 1.7
67 97 2.2
Вывод 1
2
Ввод 2
11 53 0.2
53 97 0.4
11 29 0.1
29 67 0.2
67 97 0.3
Вывод 2
2

Примечание

В первом примере пути 11, 53, 29, 97 и 11, 67, 97 имеют одинаковую минимальную длину 3.9. В первом три ребра, во втором два, поэтому ответ — 2. Прямое ребро веса 5.9 не подходит по основному критерию.

Во втором примере оба пути имеют длину 0.6: 0.2+0.4=0.1+0.2+0.30.2 + 0.4 = 0.1 + 0.2 + 0.3. Выбирается путь из двух рёбер. Сравнивать нужно точные суммы весов, а не их целые части.

Решение
Загрузка редактора…
Результат появится здесь

Черновик сохраняется в этом браузере.

Ошибка в задаче