Задание выполняется с использованием прилагаемого файла 23_21.txt.
В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром.
Найдите количество различных путей из вершины с номером 1 в вершину с номером 100, содержащих от 4 до 9 рёбер включительно. Существование хотя бы одного такого пути гарантируется.
Для выполнения этого задания следует написать программу.
Вершины графа могут быть пронумерованы не подряд. L ≤ 1000, M ≤ 1000; W ≤ 10 000. Количество строк в файле не превосходит 200. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.
Типовой пример организации данных во входном файле для графа на рисунке
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 в вершину 100, содержащих от 1 до 2 рёбер включительно, то таких путей три; верный ответ — 3.
Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла.