# Zkouska 12.6. Elektromobil

<{ForumPost(poster="sobkulir", timestamp=2017-06-12 19:44:54)}>
Dnes bola nová úloha.  
  
**Zadanie**  
Je zadaný neorientovaný, ohodnotený graf mesta s **N** vrcholmi. Ohodnotenie hrán odpovedá počtu minút, ktoré treba na presun medzi vrcholmi hrany. Máme elektromobil, ktorý je na začiatku vo vrchole **V**, má kapacitu nabitia **C** a je aktuálne nabitý na **B**. Jedna "jednotka nabitia" nám vystačí na 1 minútu cesty, takže ak chceme prejsť po hrane s hodnotou 8, musíme mať v nádrží aspoň 8 jednotiek nabitia. Niektoré mestá slúžia ako čerpacie stanice, v ktorých sa instantne elektromobil nabije na jeho maximálnu kapacitu. Takýchto miest je **B**.  
**Úloha:** Je zadaných **S** miest - showroomov, máme nájsť *najkratší sled* (hrany sa môžu opakovať) taký, ktorý začne vo vrchole **V** a navštívi v ľubovoľnom poradí všetky vrcholy z **S**. Nemáme zaručené, že takýto sled existuje.  
  
**Vstup**  
Graf dostaneme po hranách v tvare \[mesto1 mesto2 cena], kde mesto1 a mesto2 sú stringy označujúce meno mesta a cena je hodnota hrany.  
Počiatočný vrchol je na vstupe v tvare \[V C B], kde V je názov mesta počiatočného vrcholu.  
Stanice a showroomy sú zadané jednoducho ako zoznamy miest.  
  
**Výstup**  
Ak sled existuje, vypíšte ho v tvare \[cas mesto], teda pre každé mesto sledu vypíšeme čas, kedy sme sa tam dostali a jeho názov. Čas začína napr. od 00:00.  
  
**Obmedzenia**  
Veľkosť mesta: N <= 1000  
Kapacita nabitia: C <= 200  
Počet staníc: B <= 20  
Počet showroomov: S <= 10  
Pamäť max. 1GB
<{/ForumPost}>

<{ForumPost(poster="JacobSVK", timestamp=2017-06-12 20:25:43)}>
Hej myslím že tam bolo že miest je 1000, malo sa to ževraj riešiť nejakou modifikáciou BFS alebo Floyd-Warshallom, jak som počúval Holan bol celkom smutný z tej úlohy lebo zjavne veľa ľudí to nemalo perfektne, mňa skúšal Pergel i keď som ho videl prvý krát v živote, tá skúška je dosť o šťastí, Pergel písomku len tak preletel našiel mi pár protipríkladov na moje riešenie a povedal že je to tak na dva a dal mi AVL stromy delete/insert definíciu, vložiť prvky 1,23,3,4,5,6,7 a pak delete prvkov 2,4, ževraj je to taký kontrolný príklad len sa pozrel na medzikroky, troška mi nerozumel s dvojitou rotáciou pretože on to robil hneď a ja s medzikrokom ale zhodli sme sa a dal mi za dva  :D
<{/ForumPost}>

<{ForumPost(poster="abc", timestamp=2018-01-29 22:48:25)}>
No rozhodně to je NP-těžký, musím vyzkoušet 10! možností, jak ty showroomy půjdou za sebou. 10! ale není moc. Problém je, že nevim jestli s těmi nabíječkami umím spočítat Floydem opravdu nejkratší cesty. Ovšem i kdybych uměl, nefungovalo by to. Tedy vybrání nejkratší možnosti z 10! posloupností showroomů spojených nejkratšími cestami mezi nimi. Protipříklad (auto má kapacitu B=2, legenda dole):  
  
s  ---2---> a --1--> b  
 \2->ch-1/  
  
Kde s je start, a,b jsou showroomy, ch dobíječka a čísla jsou váhy hran.   
Můj algoritmus má za nejkratší cestu z s do a tu přímou. A proto když zrovna zkoumá posloupnost (s,a,b), nedostane se do b, protože již v a má vyplýtvanou baterii a cestu z s do a přes dobíječku nezkusí, protože není nejkratší.
<{/ForumPost}>

<{ForumPost(poster="abc", timestamp=2018-01-29 22:50:01)}>
To by mě zajímalo, jaké je tedy řešení
<{/ForumPost}>

<{ForumPost(poster="test", timestamp=2018-05-26 21:17:21)}>
Nepomohlo by ohodnotit hrany pred dobijeckama negativne vzhledem ke kapacite ?
<{/ForumPost}>