Zadanie

Táto úloha má tak dlhé zadanie, že by potrebovala mínus pätnásť riadkov rozprávky.

Máme krajinu a v krajine rozmiestnených niekoľko zastávok. Zastávky majú mená: reťazce 1 až 10 malých písmen anglickej abecedy. Medzi \(d\) dvojicami zastávok sa dá priamo cestovať. Pre takéto dvojice zastávok máme zadanú vzdialenosť v metroch. (Vzdialenosť je rovnaká oboma smermi.)

V našej krajine existuje \(s\) jednosmerných spojení. Každé spojenie postupne navštívi dve alebo viac zastávok. Popis spojenia obsahuje okrem zoznamu zastávok ešte tri parametre: jeho rýchlosť \(v_i\) (v metroch za sekundu), jeho periódu \(p_i\) (v sekundách) a jeho offset \(o_i\) (tiež v sekundách). Čas potrebný na presun medzi dvoma zastávkami si vieme vypočítať tak, že vzdialenosť medzi nimi vydelíme rýchlosťou a výsledok zaokrúhlime nahor na celé sekundy. Význam offsetu a periódy je nasledovný: Po trase spojenia už od nepamäti každých \(p_i\) sekúnd vyráža zo začiatočnej zastávky nový spoj. Najbližšie sa tak stane o \(o_i\) sekúnd odteraz.

Všimnite si, že pre jednoduchosť predpokladáme, že sa perióda nemení počas dňa. A taktiež sme zanedbali čas státia na zastávke: všetky naše spoje na zastávkach stoja 0 sekúnd, nastupuje a vystupuje sa za jazdy :)

Medzi spojeniami vieme na zastávkach ľubovoľne prestupovať. Na prestup nám tiež stačí nulový čas. Ak teda zastávkou prechádzajú v tom istom okamihu dva rôzne spoje, stíhame prestúpiť z jedného na druhý. Na zastávkach samozrejme môžeme na prestup aj ľubovoľne dlho čakať.

Úloha

Daný je popis siete zastávok a spojení medzi nimi. Následne nasleduje niekoľko otázok. Každá otázka je tvorená dvomi menami zastávok: odkiaľ a kam chceme ísť. Vašou úlohou je vypočítať, či sa to dá, a ak áno, v akom najkratšom čase. Presnejšie, ak sme v čase 0 na zastávke, odkiaľ ideme, v akom najskoršom čase vieme byť na zastávke, kam ideme?

Formát vstupu

V prvom riadku vstupu je číslo \(d\), udávajúce počet dvojíc zastávok, medzi ktorými sa dá priamo cestovať. V každom z ďalších \(d\) riadkov vstupu je popis jednej dvojice zastávok. Tento je uvedený vo formáte “meno1 meno2 vzdialenost”.

V nasledujúcom riadku je číslo \(s\), udávajúce počet spojení. V každom z nasledujúcich \(s\) riadkov je popis jedného spojenia. Tento je uvedený vo formáte “\(v_i\) \(p_i\) \(o_i\) \(z_i\) zastavka_1 ... zastavka_\(z_i\)”. Významy \(v_i\), \(p_i\) a \(o_i\) sú uvedené vyššie, číslo \(z_i\geq 2\) udáva počet zastávok obsluhovaných spojením. Zastávky sú navzájom rôzne a pre každú dvojicu po sebe idúcich zastávok sme na vstupe mali uvedenú ich vzdialenosť.

V nasledujúcom riadku je číslo \(q\leq 10\), udávajúce počet otázok. V každom z ďalších, posledných \(q\) riadkov vstupu je popis jednej otázky. Tento je uvedený vo formáte “odkial kam”, pričom odkial a kam sú platné mená dvoch rôznych zastávok.

 Obmedzenia

Vo všetkých vstupoch platí \(d\leq 300\,000\), ale v približne polovici vstupov je \(d\) výrazne menšie. Rôznych zastávok bude nanajvýš \(100\,000\).

Všetky vzdialenosti medzi zastávkami, rýchlosti a periódy sú kladné celé čísla neprevyšujúce \(100\,000\). Pre offsety platí \(0\leq o_i < p_i\).

Súčet všetkých \(z_i\) (teda počtov zastávok jednotlivých spojení) neprekročí \(300\,000\). Vo vstupoch s malým počtom zastávok bude aj počet spojení malý.

Optimálna cesta (ak nejaká existuje) vždy trvá menej ako 20 dní. Všetky potrebné výpočty by sa vám teda mali zmestiť do bežných celočíselných premenných.

Formát výstupu

Pre každú otázku uveďte jeden riadok a v ňom text “neda sa” ak sa z daného začiatku do daného cieľa nedá dostať, resp. text “?d ?h ?m ?s”, kde namiesto otáznikov uveďte najmenší možný počet dní, hodín, minút a sekúnd, po ktorom vieme byť v cieli cesty.

Príklad

Input:

7
skladka smetisko 350
kontajner smetisko 299
dub javor 123
javor breza 234
dub breza 45678
breza lipa 1000
topol breza 50010
6
15 600 47 3 skladka smetisko kontajner
23 10 0 3 dub breza javor
1 1234 5 4 dub javor breza lipa
4 350 35 3 dub javor breza
100 1 0 2 javor dub
10 50 0 3 topol breza lipa
3
skladka kontajner
kontajner skladka
dub lipa

Output:

0d 0h 1m 31s
neda sa
0d 0h 4m 11s

Prvé spojenie má rýchlosť \(v_i=15\) (bežná MHD), periódu \(p_i=600\) (ide raz za 10 minút) a offset \(o_i=47\). Premáva na trase skladka – (350 m) – smetisko – (299 m) – kontajner. Vzdialenosť medzi skládkou a smetiskom prekonajú spoje tejto linky za 24 sekúnd, vzdialenosť medzi smetiskom a kontajnerom za 20. Najbližšie tri spoje po tejto trati odídu od skládky o 47, 647 a 1247 sekúnd odteraz, prejdú okolo smetiska o 71, 671 a 1271 sekúnd odteraz, a svoju cestu ukončia pri kontajneri o 91, 691 a 1291 sekúnd odteraz. Ak pôjdeme prvým z nich, dostaneme sa teda ku kontajneru o 1 minútu a 31 sekúnd od začiatku.

Pozrime sa teraz na poslednú otázku: ako sa dostať od dubu k lipe?

Ako prvé odchádza už v čase 0 spojenie, ktoré rýchlosťou 23 smeruje k breze a odtiaľ k javoru. Síce by sme sa ním mohli odviezť k breze, to ale nie je veľmi dobrý nápad – prišli by sme tam až po 1986 sekundách, a ešte by sme sa museli odtiaľ dostať k lipe.

Ide nám aj priama linka okolo javora a brezy k lipe, ani tou však nie je dobrý nápad ísť. Najbližší spoj síce ide už o 5 sekúnd, je však pomalý: potrvá mu to 123 sekúnd k javoru, ďalších 234 ku breze a ďalších 1000 k lipe. Do cieľa by sme teda dorazili až po 1362 sekundách.

Najlepšie riešenie vyzerá nasledovne: Na štarte počkám 35 sekúnd, potom nasadnem na spoj idúci rýchlosťou 4 okolo javora k breze. Ten ma za 31 sekúnd privezie k javoru a za ďalších 59 k breze. Tam vystúpim. Je práve 125 sekúnd od začiatku. O ďalších 26 sekúnd, teda v čase 151, pôjde okolo brezy spoj na linke topoľ-breza-lipa. (Všimnite si, že tento spoj vyrazil na svoju cestu výrazne skôr ako my.) Ten ma za 100 sekúnd prevezie od brezy k lipe. V cieli som teda po 251 sekundách.

Našou úlohou bolo zistiť, či sa dá zo zastávky A dostať na zastávku B, a ak áno, ako najrýchlejšie to vieme spraviť. Toto je zjavne úloha grafová a zrejme bude nejak súvisieť s najkratšími cestami. Ale ako presne?

Základné pozorovanie, ktoré nám pomôže úlohu vyriešiť, je nasledovné: Predstavme si, že sme objavili dva rôzne spôsoby, ako sa zo zastávky A dá dostať na nejakú zastávku C. Prvý z nich tam príde v čase \(t_1\), druhý v čase \(t_2\) a platí \(t_1<t_2\). Pri hľadaní optimálneho presunu z A do B nám stačí zapamätať si len jeden z týchto dvoch spôsobov – ten prvý. Totiž každý spôsob, akým vieme pokračovať zo zastávky C ďalej v druhom spôsobe máme k dispozícii aj pri prvom spôsobe príchodu, a možno máme ešte aj nejaké iné možnosti navyše, ktoré by sme pri príchode v čase \(t_2\) nestihli.

Myšlienka všetkých nižšie popísaných algoritmov bude teda veľmi jednoduchá: V priebehu nášho algoritmu sa budeme snažiť zostrojiť množinu všetkých zastávok, ktoré sú dosiahnuteľné zo zastávky A. Pre každú takú zastávku si navyše vypočítame aj najskorší čas, v ktorom môžeme na danej zastávke byť.

 Predspracovanie vstupu

Už vieme, že vrcholmi nášho grafu budú jednotlivé zastávky. Na vstupe však namiesto hrán máme zadanú množinu spojení, ktoré našimi zastávkami prechádzajú. Priamo pri načítavaní vstupu však vieme každé spojenie prekonvertovať na sadu hrán – ako keby sme ho nahradili viacerými linkami, z ktorých každá premáva len z jednej zastávky spojenia na druhú, bezprostredne nasledujúcu. Všetky hrany pochádzajúce z toho istého spojenia budú mať tú istú periódu. Ich offsety vypočítame jednoducho tak, že simulujeme jednu jazdu dotyčného spojenia a zapisujeme si, kedy sme navštívili ktorú zastávku.

Pre algoritmus Bellmana a Forda (prvé z riešení uvedených nižšie) by nám stačilo uložiť si všetky hrany grafu v jednom dlhočiznom zozname. Pre Dijkstrov algoritmus (druhé, lepšie riešenie) však budeme potrebovať hrany roztriediť: v každom vrchole grafu si budeme pamätať zoznam hrán, ktoré vedú z neho von. Takéto predspracovanie uvádzame aj v nasledovnom listingu.

from collections import defaultdict
from queue import PriorityQueue

def nacitaj_vzdialenosti():
    vzdialenost = {}
    d = int( input() )
    for riadok in range(d):
        x, y, dist = input().split()
        vzdialenost[ (x,y) ] = vzdialenost[ (y,x) ] = int(dist)
    return vzdialenost

class Segment:
    def __init__(self,kam,offset,perioda,cas):
        self.kam     = kam
        self.offset  = offset
        self.perioda = perioda
        self.cas     = cas

def nacitaj_linky(vzdialenost):
    graf = defaultdict(list)

    s = int( input() )
    for riadok in range(s):
        tokeny = input().split()
        v, p, o, z = [ int(x) for x in tokeny[:4] ]
        zastavky = tokeny[4:]
        for i in range(z-1):
            dist = vzdialenost[ (zastavky[i],zastavky[i+1]) ]
            time = (dist + v - 1) // v
            graf[ zastavky[i] ].append( Segment( zastavky[i+1], o, p, time ) )
            o = (o+time) % p
    return graf

V ďalšom texte budeme počet zastávok označovať \(n\) a celkový počet hrán v našom grafe (teda súčet počtov úsekov jednotlivých spojení) budeme označovať \(m\).

 Algoritmus Bellmana a Forda

Tento algoritmus je veľmi jednoduchý. Na začiatku vieme, že na zastávke A vieme byť v čase 0, a na žiadnej inej zastávke ešte nevieme byť. Toto si zapamätáme tak, že si pre ostatné zastávky zapíšeme, že tam vieme byť v čase “nekonečno”, pričom ako nekonečno použijeme nejakú dostatočne veľkú hodnotu.

Teraz ideme tieto hodnoty postupne zlepšovať. Zlepšovanie bude prebiehať v kolách. V každom kole sa postupne (je jedno, v akom poradí) raz pozrieme na každú hranu. Predstavme si, že sa práve pozeráme na hranu zo zastávky C na zastávku D. Momentálne sa vieme na zastávku C dostať v čase \(t_c\) a na zastávku D v čase \(t_d\). Pomôže nám hrana, ktorú práve skúmame, niečo zlepšiť? Jediné, v čom nám môže táto hrana pomôcť, je, že sa pomocou nej možno vieme skôr dostať na zastávku D. Zoberime teda čas \(t_c\), počkáme na zastávke C na najbližší spoj idúci práve skúmanou hranou a zistíme, kedy tento spoj dorazí na zastávku D. Ak sme práve dostali hodnotu menšiu ako \(t_d\), zmenšíme \(t_d\) na práve vypočítanú hodnotu – práve sme objavili lepší spôsob ako docestovať z A na D.

V programe spracovanie jednej hrany vyzerá nasledovne:

def cestuj(odkial,kedy,hrana):
    # sme na zastavke "odkial" v case "kedy"
    # chceme ist hranou "hrana" do jej cielovej zastavky
    # kedy najskor tam vieme byt?

    # pockame na najblizsi spoj iduci po linke "hrana"
    if startt % hrana.perioda != hrana.offset:
        cakaj = hrana.offset - (startt % hrana.perioda)
        if cakaj < 0: cakaj += hrana.perioda
    else:
        cakaj = 0

    # odvezieme sa linkou a vysledok vratime
    return kedy + cakaj + hrana.cas

Keď už v nejakom kole nenastanú vôbec žiadne zmeny, celý proces končí. Tvrdíme, že časy, ktoré sme vypočítali, sú najlepšími možnými časmi. Teda ak si pre nejakú zastávku ešte stále pamätáme hodnotu nekonečno, nedá sa na ňu vôbec dostať, a v opačnom prípade čas, ktorý sme vypočítali, je najlepší možný.

Teraz potrebujeme spraviť dve veci: dokázať, že vyššie uvedené tvrdenie platí, a zistiť, akú má tento algoritmus časovú zložitosť.

Všimnime si ľubovoľnú zastávku X, na ktorú sa dá zo zastávky A dostať. Nech je optimálna cesta z A na X tvorená \(k\) hranami a postupne prechádza zastávkami \(X_1\)\(X_{k-1}\). Čo sa deje v našom algoritme? V prvom kole sa postupne pozeráme na všetky hrany, teda aj na hranu z A do  \(X_1\). Po prvom kole sa teda už určite vieme dostať do \(X_1\) v potrebnom čase. V druhom kole sa opäť postupne pozeráme na všetky hrany, a medzi nimi aj na hranu z \(X_1\) do \(X_2\). Po druhom kole sa teda už vieme v potrebnom čase dostať aj z A do \(X_2\). A postupne ďalej – po \(k\)-tom kole už musí byť vypočítaný čas pre zastávku X rovný optimálnemu.

Náš algoritmus je teda korektný. Navyše si uvedomme, že pre ľubovoľnú zastávku existuje optimálna cesta, pre ktorú platí \(k<n\). To je jednoduché – nikdy sa neoplatí vracať na zastávku, na ktorej sme už boli, takže existuje optimálna cesta, na ktorej sa zastávky neopakujú. Algoritmu teda bude stačiť nanajvýš \(n-1\) kôl. A keďže v každom kole sa pozeráme na \(m\) hrán, je časová zložitosť tohto algoritmu \(O(nm)\).

Implementácia spracovania jednej otázky:

def spracuj_otazku(graf,odkial,kam):

    # pre zastavku kde zaciname je vzdialenost 0
    # pre vsetky ostatne zastavky je to 2 na 60 == nekonecno
    najskorsi_prichod = defaultdict(lambda:2**60)
    najskorsi_prichod[odkial] = 0
   
    zmena = True
    while zmena:
        # zacina nove kolo, postupne sa pozerame na vsetky hrany
        zmena = False
        for odkial in graf:
            for seg in graf[odkial]:
                # zistime, ci hranou "seg" vieme nieco zlepsit

                if najskorsi_prichod[ odkial ] == 2**60: continue

                cas_v_cieli = cestuj( odkial, najskorsi_prichod[odkial], seg )
                if cas_v_cieli < najskorsi_prichod[ seg.kam ]:
                    najskorsi_prichod[ seg.kam ] = cas_v_cieli
                    zmena = True
    
    # a na zaver uz len vypiseme spravnu odpoved 

    if najskorsi_prichod[kam] == 2**60:
        print('neda sa')
    else:
        s = najskorsi_prichod[kam]
        d = s // 86400
        s %= 86400
        h = s // 3600
        s %= 3600
        m = s // 60
        s %= 60
        print('{}d {}h {}m {}s'.format(d,h,m,s))

 Dijkstrov algoritmus

Dijkstrov algoritmus počíta presne tie isté hodnoty ako algoritmus Bellmana a Forda, robí to ale šikovnejším spôsobom, a teda dosiahneme lepšiu časovú zložitosť. Existuje viacero rôznych implementácií Dijkstrovho algoritmu. Tá, ktorú si ukážeme my, bude mať časovú zložitosť \(O(m\log n)\).

Zlepšenie dosiahneme nasledovne: Namiesto toho, aby sme znova a znova prechádzali celý zoznam hrán, budeme každú hranu spracúvať len raz, “v správnej chvíli”. Takisto práve raz budeme spracúvať každú zastávku. Zastávky budeme spracúvať usporiadané podľa optimálneho času, kedy sa na ne vieme dostať. Tieto časy síce na začiatku nepoznáme, ale postupne ich budeme zisťovať a vždy budeme vedieť, ktorú zastávku spracovať ako nasledujúcu v poradí.

Na začiatku zjavne spracujeme zastávku A: pozrieme sa na všetky hrany vedúce z nej a tak zistíme nové spôsoby ako sa dostať na nejaké ďalšie zastávky. Zastávku A si následne označíme ako spracovanú.

Ako bude vo všeobecnosti vyzerať kolo tohto algoritmu? Nejaké zastávky sme už spracovali, tie nás už nezaujímajú. Ak sa už na žiadnu ďalšiu zastávku nevieme dostať, algoritmus končí. Inak sa pozrime na tie, ktoré ešte spracované nie sú, a vyberme spomedzi nich zastávku X, na ktorú sa momentálne vieme dostať (spomedzi všetkých nespracovaných) najskôr. Túto zastávku spracujeme ako nasledujúcu v poradí.

Prečo tento algoritmus funguje? Preto, že v okamihu, keď zastávku spracúvame, tak platí, že čas, ktorý sme pre ňu vypočítali, je už optimálny.

(Formálne by sme napríklad matematickou indukciou dokázali, že platí nasledovné tvrdenie: keď sme už spracovali prvých \(k\) zastávok, tak pre každú nespracovanú zastávku máme nájdený najlepší čas takej cesty na ňu, počas ktorej môžeme prestupovať len na už spracovaných zastávkach. No a následne si už len stačí všimnúť, že pre nami vybranú zastávku X už nemôže existovať ani rýchlejšia cesta, pri ktorej by sme prestupovali aj na nejakých nespracovaných zastávkach.)

Ako to celé dobre implementovať? Kľúčová operácia, ktorú potrebujeme robiť efektívne, je nájdenie zastávky X, ktorú ideme spracovať ako ďalšiu v poradí. Aby sme toto vedeli robiť rýchlo, budeme si zatiaľ nespracované zastávky udržiavať usporiadané podľa doteraz najlepšej vzdialenosti do nich.

V C++ by sme napríklad mohli ako dátovú štruktúru použiť set< pair<int,int> > Q, v ktorom by sme mali záznamy tvaru \((t,z)\) s významom “najlepší známy čas, v ktorom už vieme byť na zastávke \(z\), je \(t\)”. Nájsť nasledovnú zastávku na spracovanie vieme v čase \(O(\log n)\) tak, že sa pozrieme na Q.begin() (teda zastávku s najmenšou vzdialenosťou). Všetky výbery dokopy počas celého algoritmu nám teda budú trvať len \(O(n\log n)\).

Spracovať konkrétnu zastávku vieme v čase \(O(d\log n)\), kde \(d\) je počet hrán vedúcich z nej. Pre každú hranu skúsime zlepšiť čas pre zastávku, kam vedie. A ak sa nám to podarí, tak z Q zmažeme starý záznam pre dotyčnú zastávku a nahradíme ho novým s menšou vzdialenosťou. No a keďže každú zastávku spracujeme počas behu algoritmu najviac raz, nasčítajú sa nám časy ich spracovania na sľubovaných \(O(m\log n)\).

V našej implementácii sme použili trochu lenivejší prístup. Ako dátovú štruktúru použijeme obyčajnú prioritnú frontu (implementovanú ako haldu). Z nej síce nevieme priebežne vymazávať, ale to nám vôbec vadiť nebude – jednoducho to nebudeme robiť a keď zlepšíme čas pre nejakú zastávku, do prioritnej fronty pridáme nový záznam s novým lepším časom. A potom len pri výbere ďalšej zastávky na spracovanie dáme pozor, či nejde o zastávku, ktorú sme už skôr spracovali. Takéto záznamy jednoducho preskočíme (a teda ich vlastne až vtedy zmažeme).

V najhoršom prípade bude naša prioritná fronta obsahovať až \(O(m)\) záznamov naraz. (Totiž každú hranu v grafe spracúvame najviac raz a každé také spracovanie nám pridá najviac jeden záznam.) Všetky operácie s prioritnou frontou budú teda v čase \(O(\log m)\) a teda výsledná časová zložitosť našej implementácie bude \(O(m\log m)\).


def spracuj_otazku(graf,odkial,kam):

    najskorsi_prichod = defaultdict(lambda:2**60) # ak este nepriradil hodnotu, je to 2^60
    najskorsi_prichod[odkial] = 0

    Q = PriorityQueue()
    Q.put( (0,odkial) )
    while not Q.empty():
        kedy, kde = Q.get()
        if najskorsi_prichod[kde] < kedy: continue # uz sme ho spracovali
        for seg in graf[kde]:
            cas_v_cieli = cestuj( kde, kedy, seg )
            if cas_v_cieli < najskorsi_prichod[ seg.kam ]:
                najskorsi_prichod[ seg.kam ] = cas_v_cieli
                Q.put( (cas_v_cieli, seg.kam) )
   
    # vypis riesenia je rovnaky ako v algoritme Bellmana a Forda

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.