Úloha: Vlak

Výzkumný ústav kolejových vozidel shromáždil ve svém depu množství pokusných prototypů nákladních vagónů a chce je nyní zapojit do vlaku s jednou tažnou lokomotivou a vlak vyslat na zkušební jízdu. Díky různým technickým omezením prototypů nelze vagóny do vlaku zapojovat v libovolném pořadí a je proto možné, že ze všech vagónů v depu nelze sestavit jediný vlak. Vagón v nazveme předchůdcem vagónu w pokud vagón w může být ve vlaku zařazen bezprostředně za vagónem v. Pokud může být vagón zařazen bezprostředně za lokomotivou, počítá se lokomotiva mezi předchůdce tohoto vagónu. Pro každý vagón je znám seznam všech jeho předchůdců. Jednotlivé vagóny mají různou hmotnost a hlavní prioritou je, aby celková hmotnost vlaku, do níž se nepočítá hmotnost lokomotivy, byla co největší.

Úkolem je sestavit za daných omezení vlak s největší možnou hmotností.

Vstup

Pro jednoduchost jsou vagóny identifikovány celými čísly od 1 do N, lokomotiva má identifikátor 0.
Na vstupu je nejprve řádek s jediným kladným celým číslem N představujícím počet vagónů v depu. Dále následuje seznam N řádků, na každém řádku je specifikace jednoho vagónu, řádky (tedy i vagóny) mohou být uvedeny v libovolném pořadí. Specifikace vagónu obsahuje nejprve identifikátor vagónu, dále za mezerou celé číslo představující hmotnost vagónu a za další mezerou seznam identifikátorů všech předchůdců tohoto vagónu. Identifikátory předchůdců mohou být uvedeny v libovolném pořadí, jsou navzájem odděleny jedinou mezerou.

Výstup

Výstup obsahuje dva řádky. Na prvním řádku jsou identifikátory vozů hledaného vlaku v pořadí od začátku vlaku včetně lokomotivy (řádek začíná nulou), identifikátory jsou odděleny jedinou mezerou. Na druhém řádku je hmotnost hledaného vlaku. Pokud dva nebo více hledaných vlaků mají stejnou hmotnost, vypíše se pouze ten z nich, jehož identifikace je nejmenší v lexikografickém uspořádání podle čísel vagónů. Např. z vlaků 0 3 6, 0 3 1 4 2, 0 3 1 5 se vybere vlak 0 3 1 4 2 (viz př. 4 níže).

Poznámka

Maximální počet vagónů v depu je 30, úloha je řešitelná pomocí přímého probírání všech možností.

Příklad 1

Vstup:

5
1 50 0 4
2 30 1 5
3 100 4 0
4 40 0 3
5 120 4

Výstup:

0 3 4 5 2 
290

Příklad 2

Vstup:

4
1 100 2 3 4
2 100 1 3 4
3 100 1 2 4
4 100 1 2 3 

Výstup:

0  
0

Příklad 3

Vstup:

5
1 10 0 
2 10 1 3 4
3 10 1 2 4 
4 10 1 2 3 
5 90 0 

Výstup:

0 5  
90

Příklad 4

Vstup:

6
3 80 0
2 20 3 4
4 30 1
1 10 3
6 60 3
5 50 1

Výstup:

0 3 1 4 2 
140

Příklad 5

Vstup:

20
1 90 11 16 19
2 52 3 7 9 12 15 17
3 97 2 5 6 9 16 20
4 85 0 3 7 13
5 74 11
6 65 0 4 9 14 16
7 89 1 5 16
8 72 3
9 71 12 14 20
10 64 5 6 12 16 17
11 97 0 15
12 82 2 6 9 13 15 19
13 52 5 11 12 15 18
14 85 1 6 10 19
15 87 0 1 6
16 63 6 7 20
17 92 8 10 13 16 17 19
18 81 6 9 14
19 83 3
20 72 7 10 11 19

Výstup:

0 4 6 3 19 1 15 11 5 7 20 16 10 14 9 18 13 17 2 12 
1481