Problem H
Ссылки
Languages
en
et
is
ja
lv
pl
ru
Грейс собирается прочитать некую научную книгу. Она привыкла всегда читать все книги-первоисточники, на которые ссылается изначальная книга, а затем на первоисточники, на которые ссылались они, и так далее. Из-за этого она обычно в итоге читает очень много книг вдобавок к той, которую хотела прочесть изначально.
Библиотекари постоянно жалуются на то, что Грейс берет в библиотеке слишком много книг. Чтобы их поменьше расстраивать, Грейс хочет найти порядок прочтения книг, при котором суммарное время удержания книг дома было бы наименьшим.
Всего Грейс необходимо прочитать $N$ разных книг. Книги пронумерованы от $1$ до $N$, а на прочтение книги $i$ уходит $K_ i$ минут. Каждая книга $i$ содержит список ссылок, состоящий из $F_ i$ книг. Книга, которую Грейс собиралась прочитать изначально, имеет номер $1$. Прежде чем начать читать книгу номер $1$, Грейс взяла из библиотеки все $N$ книг на дом.
Процесс прочтения каждой книги у Грейс проходит следующим образом:
-
Сначала она открывает книгу и сразу же читает список ссылок. Это занимает у неё одну минуту.
-
Затем она прочитывает все книги в списке ссылок, в любом порядке на её усмотрение.
-
После этого она читает саму книгу, и возвращает её в библиотеку. Это занимает ещё $K_ i$ минут.
Вам необходимо найти наименьшую возможную сумму времен хранения всех книг дома, при условии что Грейс будет читать их в оптимальном порядке. Книги могут иметь пустые списки ссылок. Каждая книга, кроме книги номер $1$ присутствует ровно в одном списке ссылок. Также известно, что ссылки не образуют циклов.
Ввод
На первой строке ввода дано целое число $N$ ($1 \le N \le 100\, 000$). Далее следут $N$ строк, по одной на каждую книгу от $1$ до $N$. На каждой из этих строк дано целое число $K_ i$ ($1 \le K_ i \le 1\, 000$) – количество минут, необходимое для прочтения книги. Затем дано целое число $F_ i$ ($0 \le F_ i < N$), за которым следуют $F_ i$ целых чисел – номера книг, на которые ссылается книга $i$.
Вывод
Вывести одно целое число – минимальное суммарное время удержания всех книг.
Ограничения
Тесты разделены на группы. Очки за группу даются только если корректно решены все тесты в группе.
|
Группа |
Очки |
Ограничения |
|
1 |
20 |
$1 \le N \le 10, 1 \le K_ i \le 1000$ |
|
2 |
30 |
$1 \le N \le 50, 1 \le K_ i \le 10$, $F_ i \le 5$ |
|
3 |
20 |
$1 \le N \le 100\, 000, 1 \le K_ i \le 1000, F_ i \le 5$ |
|
4 |
30 |
$1 \le N \le 100\, 000, 1 \le K_ i \le 1000$ |
Объяснение примера 1
минута 1: открыть книгу 1
минута 2: открыть книгу 2
минута 3: открыть книгу 4
минута 4: закрыть книгу 4 (время удержания – 4 минуты)
минута 14: закрыть книгу 2 (время удержания – 14 минут)
минута 15: открыть книгу 3
минута 16: открыть книгу 5
минута 17: закрыть книгу 5 (время удержания – 17 минут)
минута 37: закрыть книгу 3 (время удержания – 37 минут)
минута 38: закрыть книгу 1 (время удержания – 38 минут)
| Пример ввода 1 | Пример вывода 1 |
|---|---|
5 1 2 2 3 10 1 4 20 1 5 1 0 1 0 |
110 |
