Задача №1348. Алхимия
Известны K видов веществ и N типов алхимических реакций. Каждая реакция по набору входных веществ продуцирует набор выходных. Проведение каждой реакции требует фиксированного времени. Любые вещества, полученные в результате реакций, можно выделять в чистом виде для отдельного использования. Каждого вещества всегда достаточно для любого использования. Вещество, полученное в результате только что закончившейся реакции, можно сразу же использовать в других реакциях. Реакции могут проходить одновременно.
Напишите программу, которая по информации об известных веществах и реакциях определяет за какое наименьшее время можно получить целевое вещество.
Первая строка входного файла содержит четыре целых числа: K (3≤K≤250) — количество веществ, N (3≤N≤500) — количество реакций, M (1≤M<K) — количество имеющихся сначала веществ, а также номер целевого вещества.
Далее следуют N блоков, которые описывают реакции. Каждый блок состоит из трех строк: первая содержит натуральное число — время, необходимое для проведения реакции, вторая строка — количество веществ, которые вступают в реакцию, и перечень этих веществ, третья строка — количество веществ, которые образовываются в результате реакции, и их перечень.
Вещества, имеющиеся сначала, имеют номера от 1 до M, а все остальные — от M+1 до K. Сумма времен проведения всех реакций не превышает 2∙109.
Единственная строка выходного файла должна содержать целое число — найденное минимальное время, за которое может быть получено целевое вещество.
Если получить целевое вещество невозможно, единственная строка выходного файла должна содержать число -1.
Для приведенного примера входных данных, целевое вещество 4 можно получить, если на протяжении первых трех единиц времени провести реакцию 2, а после этого на протяжении двух единиц времени провести реакцию 3. Таким образом, за 5 единиц времени будет получено требуемое вещество.
4 3 1 4 8 1 1 1 4 3 1 1 2 2 3 2 2 1 3 1 4
5