Zkouska 12.6. Elektromobil

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

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

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ší.

To by mě zajímalo, jaké je tedy řešení

Nepomohlo by ohodnotit hrany pred dobijeckama negativne vzhledem ke kapacite ?