|
Дистанционный практикум по программированию
|
||||||||||
|
|
|||||||||||
| Здравствуйте, Гость! Войдите с паролем или зарегистрируйтесь. |
1586. Ant and Apples
|
| Статистика | Послать на проверку | Задачу добавил debug |
|
The building of Saratov department of H&H company is situated at the beautiful place near the bank of the river Volga. In the building courtyard there is an ant hill, where ant known as Apache leaves. The ant is very small and he wants to grow up as quickly as possible. There is an apple-tree nearby the ant hill, and Apache decided to eat all of the apples to come closer to his goal. All branches of the apple-tree grow up, and if branches were splitted once, they never grow together again. Each branch is finished either by a fork or by an apple. The branches of the tree are pretty long, so ant's vigor quickly decreases while he is moving to the next apple. For each centimeter ant looses one point of energy of energy contained in this apple. Eating an apple increases ant's energy by certain amount. If energy level will fall below zero, Apache will die. Your task is to help Apache to survive and find out how much energy he need to accumulate before the trip to successfully get all apples from the tree and return back. Note, ant can crawl along each branch only for two times. The ant starts and finishes his movement at the beginning of the branch number one. The branch number one is considered as a stem of the tree. Входные данные The first line of the input contains integer number N (1 ≤ N ≤ 1000) — the number of branches. The following N lines contain information about the apple-tree and apples. Each line describes the corresponding branch of the tree. The branch description consists of the following. The first number is integer L (1 ≤ L ≤ 50000) — the length of the branch. Then Q follows — the amount of branches which grow from the end of the current branch. The following Q numbers are numbers of these branches. If Q equals to zero, the third number E (0 ≤ E ≤ 50000) gives the amount of energy of the apple at the end of this branch. Выходные данные Write to the output one integer number — the minimal possible number of energy points ant should accumulate to be able to eat all apples and return to the ground. Пример Входные данные 8 Выходные данные 15
|
| Статистика | Послать на проверку | Обсуждение задачи | Автор/источник: |
| Задачи с соревнований и сборов / | Сборы в Перми 2009 / | 07.07.09 Большой контест / |
| 1585. D - Road to Home | 1586. | 1587. F - Square | 1588. G - Pair | 1589. H - The Fence |
| время генерации 0.719 сек. | |
| © Copyright ВоГУ, АВТ, Носов Д.А., Андрианов И.А. |