Zkouška 9.6 – Holan - Pergel

Je dán neorientovaný ohodnocený graf místa s $N$ vrcholy. Ohodnocení hran udává počet vody, kterou spotřebuje karavana při cestě po této hraně

Máme karavanu, která:

• začíná ve vrcholu $V$,

• má maximální kapacitu vaků s vodou $C$

• Počáteční stav vody $Z$

Řekněme, že karavana spotřebuje litr vody na hodinu

Některá místa jsou oázy, kde se doplní vaky s vodou na maximum, těchto oáz je nejvýše $O$ a můžeme je navštívit opakovaně

Je dána množina $U$ míst (k navštívení), které je nutné navštívit v libovolném pořadí. Cílem je najít libovolný časový sled pohybu karavany po grafu (hrany se mohou opakovat), který:

• začíná ve vrcholu $V$,

• navštíví všechna města ze seznamu $S$,

• zohledňuje omezení karavany a nutnost doplnění vody.

Není zaručeno, že takový sled existuje.

Vstup

1. Hrany grafu ve tvaru: $[\text{místo1} \ \text{cena} \ \text{místo2}]$

2. Počáteční informace o karavaně ve tvaru: $[V \ C \ B]$

   • $V$ je název počátečního města

   • $C$ je maximální kapacita vaků s vodou

   • $Z$ je počáteční stav vody

3. Seznam oáz (názvy míst)

4. Seznam míst k navštívení (názvy míst, které je třeba navštívit)

Výstup

Pokud existuje požadovaný sled, vypište jej ve formátu: $[místo \ čas]$

Pro každé místo, které v rámci sledu navštívíme, vypíšeme:

• název města.

• čas příjezdu (např. 00:00, 01:20, atd.),

Čas začíná od 00:00.