Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Производство деталей

(Время: 2 сек. Память: 32 Мб Сложность: 48%)

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

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

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

Входные данные

Первая строка входного файла INPUT.TXT содержит число n (1 ≤ n ≤ 100000) – количество деталей двигателя. Вторая строка содержит n натуральных чисел p1, p2 … pn , определяющих время изготовления каждой детали в секундах. Время для изготовления каждой детали не превосходит 109 секунд.

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

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

Выходные данные

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

Примеры

INPUT.TXTOUTPUT.TXT
13
100 200 300
1 2
0
2 2 1
300 2
2 1
22
2 3
1 2
0
5 2
2 1
34
2 3 4 5
2 3 2
1 3
0
2 1 3
9 3
3 2 1

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Базовые понятия
 Представление графа
 Поиск в глубину
 Поиск в ширину
 A. Друзья
 B. Скачки
 C. Дерево
 D. Банкет
 E. Компоненты связности
 F. Удаление клеток
 G. Укладка плитки
 H. Раздел империи
 I. Покраска лабиринта
 J. Построение
 K. Рекурсия
 L. Производство деталей
 M. Доказательство теоремы
 N. Го
 O. Радио
 P. Конная прогулка

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru