od sobkulir » 12. 6. 2017 19:44
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
Dnes bola nová úloha.
[b]Zadanie[/b]
Je zadaný neorientovaný, ohodnotený graf mesta s [b]N[/b] 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 [b]V[/b], má kapacitu nabitia [b]C[/b] a je aktuálne nabitý na [b]B[/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]B[/b].
[b]Úloha:[/b] Je zadaných [b]S[/b] miest - showroomov, máme nájsť [i]najkratší sled[/i] (hrany sa môžu opakovať) taký, ktorý začne vo vrchole [b]V[/b] a navštívi v ľubovoľnom poradí všetky vrcholy z [b]S[/b]. Nemáme zaručené, že takýto sled existuje.
[b]Vstup[/b]
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.
[b]Výstup[/b]
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.
[b]Obmedzenia[/b]
Veľkosť mesta: N <= 1000
Kapacita nabitia: C <= 200
Počet staníc: B <= 20
Počet showroomov: S <= 10
Pamäť max. 1GB