Задача G регионального тура (online тестирование). Производство деталей

Первоисточник: Региональный этап Всероссийской олимпиады школьников по информатике 2009 - 2010 учебного года

Задачу добавил: alef

Успешно сдано решений: 13

Имя входного файла: input.txt
Имя выходного файла: output.txt
Максимальное время работы на одном тесте: 2 c
Максимальный объем используемой памяти: 64 Мб
Максимальная оценка: 100 баллов

Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p_i секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу – за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

Требуется написать программу, которая по заданным зависимостям порядка производства между деталями найдет наименьшее время, за которое можно произвести деталь с номером 1.

Формат входных данных

Первая строка входного файла содержит число n (1 ≤ n ≤ 100000) – количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂ … p_n , определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 10⁹ секунд.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей k_i, которые требуются для производства детали с номером i, а также их номера. Сумма всех чисел k_i не превосходит 200000.

Известно, что не существует циклических зависимостей в производстве деталей.

Формат выходных данных

В первой строке выходного файла должны содержаться два числа: минимальное время (в секундах), необходимое для скорейшего производства детали с номером 1 и число k деталей, которые необходимо для этого произвести. Во второй строке требуется вывести через пробел k чисел – номера деталей в том порядке, в котором следует их производить для скорейшего производства детали с номером 1.

Примеры входных и выходных данных

input.txt - 1

3

100 200 300

1 2

0

2 2 1

output.txt - 1

300 2

2 1

input.txt - 2

2

2 3

1 2

0

output.txt - 2

5 2

2 1

input.txt - 3

4

2 3 4 5

2 3 2

1 3

0

2 1 3

output.txt - 3

9 3

3 2 1

Система оценивания

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

 

Сдать задачу

Задать вопрос жюри по этой задаче