Кратчайший путь

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

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

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

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

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

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

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

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

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

Примеры

Ввод 1
100 12 1.0
6 7 7.0
6 1 1.0
1 7 5.5
7 100 2.0
4 100 8.0
1 100 12.0
1 4 2.5
Вывод 1
7
Ввод 2
1 5 3.2
5 100 4.1
1 100 7.9
5 9 1.0
9 100 2.5
Вывод 2
6

Примечание

В первом примере кратчайший путь 1→7→1001 \to 7 \to 100 имеет длину 5.5+2.0=7.55.5 + 2.0 = 7.5, её целая часть равна 77. Путь 1→4→1001 \to 4 \to 100 длиннее: 2.5+8.0=10.52.5 + 8.0 = 10.5.

Во втором примере кратчайший путь состоит из трёх рёбер: 1→5→9→1001 \to 5 \to 9 \to 100, его длина 3.2+1.0+2.5=6.73.2 + 1.0 + 2.5 = 6.7.

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

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

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