К содержанию
К списку задач

ЕГЭ 23 · Анализ графов

Анализ графов

(Л. Шастин) В текстовом файле содержится описание ациклического ориентированного взвешенного графа. В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W). L и M – номера вершин графа, W – вес ребра, ведущего из вершины L в вершину M. Таким образом, количество строк в файле равно количеству рёбер в графе. Две вершины графа не могут быть соединены более чем одним ребром. Найдите и запишите в ответе количество различных путей из вершины с номером 3003 в вершину с номером 3308, проходящих через вершину с номером 3112 и не проходящих при этом через вершину с номером 3207. Существование хотя бы одного такого пути гарантируется. Для выполнения этого задания следует написать программу. Вершины графа могут быть пронумерованы не подряд. L ≤ 10000, M ≤ 10000; W ≤ 100. Количество строк в файле не превосходит 100 000. Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

23.txt23.txtТекстовый файл · 1,3 МБ

Запишите ответ в формате, указанном в условии.