You may remember the Spamway messaging service. Spamway uses a pyramid scheme of zombie computers to solicit and receive orders for their fine products. However, Spamway has a problem – all its zombies have gone on strike for better RAM. Hence, Spamway has recruited replacement scab zombies so that they can continue doing business during the strike. These scab zombies are very disorganized and hence are not very good at networking.
Your job is to organize the scab zombies so that Spamway can solicit and receive product orders in the minimum amount of time. Specifically, you are to assign to each zombie a list of subordinates so that:
To initiate a round of ordering, the head zombie will simultaneously send a message to all of its subordinates requesting a list of purchase orders. A scab zombie, upon receiving such a message, will make a similar request of all of its subordinates. After receiving a reply from all of its subordinates, the scab zombie will combine the purchase lists contained therein with the list of purchase orders it received and send the combined purchase list to its superior.
So that you can organize the zombies, you need to know a few things:
Input begins with an integer value n indicating the number of scab zombies that have been hired (not counting the manager acting as head zombie), 1 ≤ n ≤ 99. This integer is followed by n + 1 lines, each of which identifies the zombie zzz time for one particular zombie, followed by the number of zombies that can be reliably contacted and then a list of those zombies. The first line describes the head zombie, and the remaining n lines describe zombies Z1 through Zn, in that order.
Output should consist of a single integer value indicating the total amount of time that is needed to send and receive the data for a single round of ordering. While there may be several possible zombie organizations, you are to find and report the time for the optimal one.
3 0 2 1 3 50 1 0 7 1 3 3 2 0 2
There is only one organisation available: Z0’s subordinates are Z1 and Z3; Z1 and Z2 have no subordinates, and Z3’s only subordinate is Z2. When Z0 decides to initiate a round of ordering (let us call this time ”0”), it sends off an order request to Z1 and Z3. At time 10, Z1 and Z3 receive the message. Z3 takes three seconds to read the message, and, at time 13, Z3 has read the message and it fires off a request to its subordinate, Z2. At time 23, Z2 receives Z3’s message, and has ot think for seven seconds. At time 30, Z2 is done thinking. Z2 has no subordinates, so it sends its order list to its superior Z3. At time 40, Z3 receives the order list, and has to think for three seconds. At time 43, then, Z3 combines Z2’s order list with its own and sends the combined order list to Z0, and it is received at time 53. At time 60, after fifty seconds of thought, Z1 has finished reading Z0’s initial message. Z1 promptly sends its order list to Z0, which receives the list at time 70. After receiving this message, Z0 is in possession of all of the purchase orders sent to Spamway, thus terminating the round of ordering.