Автор: | Центральная предметно-методическая комиссия по информатике | Ограничение времени: | 2 сек | |
Входной файл: | details.in | Ограничение памяти: | 256 Мб | |
Выходной файл: | details.out | |||
Максимальный балл: | 100 |
Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за pi секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.
Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.
Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдет наименьшее время, за которое можно произвести деталь с номером 1.
Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.
Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.
Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.
Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p1,p2…pn, определяющих время изготовления каждой детали в секундах.
Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей ki, которые требуются для производства детали с номером i, а также их номера.
Известно, что не существует циклических зависимостей в производстве деталей.
В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел — номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.
1≤n≤100000, 1≤pi≤109
Сумма всех чисел ki не превосходит 200000.
№ | Входной файл (details.in ) |
Выходной файл (details.out ) |
---|---|---|
1 |
|
|
2 |
|
|
3 |
|
|