Многопроцессорные системы

(М. Попков) На предприятии «ЭлектроТех» осуществляется сборка сложных электронных устройств, включающих множество этапов, которые могут выполняться параллельно или последовательно. Будем говорить, что этап B зависит от этапа A, если для выполнения этапа B необходимы результаты выполнения этапа A. В этом случае этапы могут выполняться только последовательно.

Информация об этапах сборки представлена в электронном виде в виде таблицы. В первом столбце таблицы указан идентификатор этапа (ID), во втором столбце таблицы – время его выполнения в миллисекундах, в третьем столбце перечислены с разделителем «;» ID этапов, от которых зависит данный этап. Если этап является независимым, то в таблице указано значение 0.

Определите максимальную продолжительность отрезка времени (в мс), в течение которого возможно одновременное выполнение максимального количества этапов, при условии, что все независимые друг от друга этапы могут выполняться параллельно, а время окончания работы всех этапов минимально.