Myslím, že to byla nová úloha.
Zadání:
Ve městě jsou ulice ohodnocené délkou a nebezpečností. Úkolem je najít co nejbezpěčnější cestu mezi dvěma místy ve městě. Nebezpečnost cesty závisí pouze na nebezpečnosti nejnebezpečnější ulice po cestě a pokud je víc stejně nebezpečných cest, chceme tu nejkratší. Je zaručeno, že aspoň jedna cesta existuje.
**
Vstup:**
seznam ulic:* odkud, kam, bezpečnost (ve tvaru 2^31 - # prepadeni), délka*
start a cíl cesty
křižovatek <= 1000
pamět: 1GB
Výstup:
nebezpečnost nejbezpečnější cesty výpis ulic kterýma prochází zase odkud, kam
Byla jsem u Pergela, mojí písemku předtím očividně nečetl, chtěl po mě abych stručně shrnula svoje řešení.
Řešila jsem to tak, že jsem si seřadila hrany podle nebezpečnosti a postupně odebírala ty nejhorší (když jich bylo víc stejně nebezpečných odebrala jsem všechny) a zkoumala, jestli start a cíl jsou v té samé komponentě. Potom už nebyly, přidala jsem poslední potřebný našla nejkratší cestu pomocí Dijkstry. Vůbec se neptal na podrobnosti, reprezentaci čehokoliv nebo jak bych zkoumala ty komponenty, případně co složitost nebo paměť. Jen po mě chtěl ukázat jednu větu na papíře a řekl to vypadá věrohodně.
Z ústní mi dal dynamické programování a ptal se jaký znám použití, uzávorkování násobení matic je prý jeho nejoblíbenější.
Osobně jsem z toho měla smíšené pocity, Pergel vypadal, že to chce mít hlavně rychle za sebou (to jsem byli dva), taky to vypadalo že by se v tom i vrtal, ale říkal, že tohle řešení ještě neviděl, takže mi věří, že to tam všechno je. Ani u ústní se v tom moc nevrtal, potom řekl že jsem mu všechno řekla, algoritumus byl taky v pořádku, ale že na jedničku se mu to nezdá a dal mi dvojku. Já byla ráda že to mám za sebou, ale příde mi, že je to hodně o jeho náladě a pocitu.