Контрольная вершина и обход

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

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

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

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

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

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

Гарантируется, что длина искомого пути не является целым числом.

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

Выведите одно целое число — целую часть длины кратчайшего из таких путей.

Примеры

Ввод 1
11 97 0.1
11 53 1.5
53 67 0.1
67 97 0.1
53 97 3.9
Вывод 1
5
Ввод 2
11 53 1.9
53 97 1.9
11 67 0.1
67 53 0.1
11 97 0.2
Вывод 2
3

Примечание

В первом примере подходит путь 11, 53, 97 длиной 1.5+3.9=5.41.5 + 3.9 = 5.4, ответ — 5. Прямое ребро не проходит через 53, а более короткий путь через 53 и 67 нарушает запрет. Во втором примере длина подходящего пути равна 1.9+1.9=3.81.9 + 1.9 = 3.8, ответ — 3.

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

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

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