6. Ázijec a továreň na čokoládu vzorové riešenie

Zadanie

Keď si Baklažán nedávno vychutnával tabuľku svojej obľúbenej čokolády, objavil v nej zlatý lístok, ktorý mu garantoval návštevu Wonkovej továrne na čokoládu. So skupinou ďalších detí sa nadšený vydal do útrob obrovského komplexu. A že ho tam čakalo prekvapení – spievajúci trpaslíci, veveričky lúskajúce orechy, žuvačky každej chuti, riečna sieť tečúcej čokolády…

Deti, ktoré našli zlatý lístok sú však rozmaznané, nenásytné, pyšné a Willimu Wonkovi lezú poriadne na nervy. A Baklažán tomu tiež veľmi nepomáha, občas totiž odmieta pochopiť, čo sa mu snažíte povedať. Preto keď už tretíkrát odpovedal na Willyho otázku, či chce jahodovú alebo malinovú čokoládu, áno, Willy sa nahneval a zhodil ho do burácajúcej čokoládovej rieky.

Baklažán sa však tak ľahko nevzdáva. Rozhodol sa doplávať na ďaľšiu zastávku Wonkovej exkurzie. Otázka však je, či to stihne. Každý úsek riečnej siete je síce rovnako dlhý, tečie v ňom však rôzne hustá čokoláda. Platí, že preplávanie úseku s hustotou \(w\) bude Baklažánovi trvať čas \(w\). Jeho cieľom je dostať sa na plánované miesto stretnutia čo najrýchlejšie.

Plávanie v čokoláde má však ešte jednu veľkú (ne)výhodu. Chcete ochutnať každý druh čokolády, v ktorej plávate. Baklažán vie, že ak ochutná viac ako \(c\) čokolád, dostane hyperglykemický šok a do cieľa už nedopláva. Môže teda preplávať cez najviac \(c\) úsekov. Naviac, plávanie s plným bruchom je čoraz ťažšie a ťažšie. Chcel by preto, aby hustota čokolád, v ktorých pláva, celý čas stúpala, aby sa mu plávalo ľahšie¹.

Úloha

Riečnu sieť tečúcej čokolády si môžete predstaviť ako graf, ktorý má \(n\) vrcholov (očíslovaných od 1 po \(n\)) a \(m\) orientovaných hrán. Každá hrana predstavuje jeden úsek rieky a má priradené číslo \(w_i\) – hustotu daného úseku. Platí, že na preplávanie úseku s hustotou \(w_i\) je potrebný čas \(w_i\).

Vaše riešenie musí odpovedať na \(q\) otázok. Každá otázka je tvorená troma celými číslami \(a_i\), \(b_i\) a \(c_i\) – ako najrýchlejšie sa vie Baklažán dostať z vrcholu \(a_i\) do vrcholu \(b_i\), ak môže preplávať cez najviac \(c_i\) úsekov a hustoty úsekov musia počas celej plavby stúpať?

Formát vstupu

Prvý riadok vstupu obsahuje tri celé čísla \(n\), \(m\) a \(q\) (\(2 \leq n \leq 150\), \(0 \leq m \leq 3\,000\), \(1 \leq q \leq 1\,000\)) – počet vrcholov a hrán grafu a počet otázok, na ktoré musíte odpovedať.

Nasledujúcich \(m\) riadkov popisuje hrany grafu. Každá hrana je popísaná troma číslami \(x_i\), \(y_i\) a \(w_i\). Táto trojica reprezentuje orientovanú hranu z vrchola \(x_i\) do vrchola \(y_i\) s hustotou \(w_i\). Medzi dvojicou vrcholov môže viesť aj viacero hrán, dokonca aj v tom istom smere. Platí, že \(1 \leq x_i, y_i \leq n\) a \(1 \leq w_i \leq 3\,000\). Naviac, žiadne dve hrany nemajú rovnakú hustotu \(w_i\).

Každý z nasledujúcich \(q\) riadkov obsahuje tri čísla \(a_i\), \(b_i\) a \(c_i\), ktoré popisujú otázky, na ktoré máte odpovedať – ako najrýchlejšie sa vie Baklažán dostať z vrchola \(a_i\) do vrchola \(b_i\) ak môže použiť najviac \(c_i\) hrán, ktorých hustoty postupne stúpajú? Pre každú otázku platí, že \(1 \leq a_i \neq b_i \leq n\) a \(0 \leq c_i \leq m\).

Úloha má 8 sád testovacích vstupov. Pre jednotlivé sady navyše platia nasledovné obmedzenia:

číslo sady	\(1\)	\(2\)	\(3\)	\(4\)	\(5\)	\(6\)	\(7\) a \(8\)
\(n \leq\)	\(8\)	\(20\)	\(20\)	\(50\)	\(50\)	\(150\)	\(150\)
\(q \leq\)	\(1\)	\(1\)	\(1000\)	\(1\)	\(1000\)	\(1\)	\(1000\)

Formát výstupu

Pre každú otázku vypíšte na samostatný riadok odpoveď v poradí, v akom sa otázky objavili na vstupe. Pokiaľ Baklažán nevie splniť zadanie niektorej otázky, vypíšte -1.

Príklady

Input:

6 10 3
1 2 2
2 1 11
2 3 3
1 3 7
1 6 5
6 4 4
4 5 6
3 5 1
4 2 10
3 4 8
1 4 2
1 4 3
2 5 5

Output:

15
13
-1

Ak sa chceme dostať z vrchola 1 do vrchola 4 použitím najviach dvoch hrán, máme iba jednu možnosť, ísť cez vrchol 3. Cesta cez vrchol 6 totiž nespĺňa podmienku, že hustota hrán má postupne rásť.

Z vrchola 2 sa do vrchola 5 nevieme dostať bez toho aby sme neporušili podmienku zo zadania.

---

1. Niečo, niečo, fyzika, niečo, niečo, vztlak…↩

Prvý krok k riešeniu je vždy poriadne si prečítať zadanie a zistiť, čo od nás vlastne chce. V tomto prípade je tento krok obzvlášť dôležitý, lebo zadanie je pomerne komplikované. Skúsme si teda spoločne zopakovať, čo je našou úlohou.

Na vstupe máme orientovaný graf, ktorého každá hrana má kladnú váhu \(w_i\). Postupne dostaneme \(q\) otázok, každá má tvar: Aká je najkratšia cesta medzi vrcholmi \(a_i\) a \(b_i\), ktorá ide cez najviac \(c_i\) hrán a váhy týchto hran navyše celú dobu stúpajú?

Hľadanie cesty s obmedzeným počtom hrán

Keďže úloha obsahuje pomerne veľké množstvo parametrov, na ktoré si musíme dávať pozor, skúsme si ju zjednodušiť. Napríklad, pre začiatok nemusíme uvažovať o tom, že hrany na výslednej ceste musia rásť. A takisto sa nezaoberajme tým, že máme viacero otázok. Ak dokážeme úlohu vyriešiť pre jednu otázku, prinajhoršom tento postup \(q\) krát zopakujeme.

Nová úloha, ktorú riešime preto znie: Nájdite dĺžku najkratšej cesty medzi vrcholmi \(\boldsymbol{x}\) a \(\boldsymbol{y}\), ktorá neobsahuje viac ako \(\boldsymbol{c}\) hrán.

Takéto zadanie vyzerá oveľa jednoduchšie. Máme predsa presne daný začiatok aj koniec a poznáme aj počet hrán na ceste, ktorú hľadáme. Mohli by sme sa teda pokúsiť siahnuť po niektorom z klasických algoritmov na hľadanie najkratších ciest – Dijkstrov algoritmus, poprípade prehľadávanie do šírky. Obom však niečo chýba, Dijkstra sa nepozerá na počet hrán v ceste a prehľadávanie do šírky zase nepracuje s váhami hrán. Navyše, keď sa pozrieme do zadania, vidíme, že hodnoty \(n\) a \(m\) sú pomerne malé. Možno teda vôbec nepotrebujeme tak rýchle riešenie.

Pozrime sa na to inak. Čo by sa stalo, keby sa \(c=0\)? Úloha by bola zrazu veľmi jednoduchá. Ak môžeme prejsť po 0 hranách, z vrchola \(x\) sa dostaneme akurát do vrchola \(x\) tým, že sa nepohneme. A keby bolo \(c=1\)? V tom prípade by sme z \(x\) mohli prejsť po jednej hrane. Vedeli by sme sa teda pozrieť na všetky hrany, ktoré z \(x\) vedú a to by nám ukázalo vrcholy, do ktorých sa vieme dostať. Naviac, ak by do jedného vrchola viedlo z \(x\) viacero hrán, vybrali by sme tú kratšiu.

A čo s \(c=2\)? V tom prípade by sme sa museli pozrieť na vrcholy, do ktorých sme sa vedeli dostať z \(x\) na jednu hranu a pridať hranu ďalšiu. Opäť by sme teda získali všetky vrcholy, do ktorých sa vieme dostať z \(x\) s pomocou 2 hrán. Naviac vieme zistiť aj najkratšiu dĺžku ciest do týchto vrcholov.

V tomto momente by malo byť jasné, že tento postup vieme zovšeobecniť. Ak poznáme najkratšie cesty s \(k\) hranami, ktoré vedú z vrchola \(x\), tak ich vieme použiť na vypočítanie najkratších ciest s \(k+1\) hranami.

Pozrime sa na to ešte trochu bližšie. Majme dvojrozmerné pole dlzka[][], pričom na indexe dlzka[p][r] si pamätáme dĺžku najkratšej cesty vedúcej z vrchola \(\boldsymbol{x}\) do vrchola \(\boldsymbol{p}\), ktorá prejde cez práve \(\boldsymbol{r}\) hrán. Ostáva už len vypočítať túto hodnotu. Zoberme si nejakú hranu, ktorá vedie z vrchola \(p'\) do vrchola \(p\) a má dĺžku \(w\). Potom môžeme povedať, že dlzka[p][r] = w + dlzka[p'][r-1]. Teda ak k dĺžke najkratšej cesty z vrchola \(x\) do vrchola \(p'\), ktorá vedie cez \(r-1\) hrán pripočítame ďalšiu hranu, ktorá z \(p'\) vedie do vrchola \(p\) a má dĺžku \(w\), dostaneme cestu z \(x\) do \(p\).

Táto cesta síce nemusí byť najkratšia, ak ale zoberieme všetky hrany, ktoré vedú do vrchola \(p\) a zoberieme minimum z týchto hodnôt, určite nájdeme najkratšiu cestu z \(x\) do \(p\), ktorá ide cez \(r\) hrán.

Takéto riešenie vieme dokonca veľmi jednoducho naprogramovať. Stačia nám na to dva for-cykly. Vonkajší bude určovať, koľko hrán chceme použiť – teda najskôr 1, potom 2, 3… a vnútorný cyklus bude prechádzať cez všetky hrany a postupne ich skúsi pridať k cestám o jedno kratším.

struct hrana {
    int x, y;  // hrana vedie z vrcholu x do vrcholu y
    int w;     // hrana ma vahu w
};

vector<hrana> hrany;
int x;            // zaciatocny vrchol
int dlzka[n][m];  // najkratsia cesta z vrchola x do vrchola n s m hranami
                  // na zaciatku vyplnena dostatocne velkymi hodnotami

for(int r = 1; r <= m; r++) {
    for(int j = 0; j < hrany.size(); j++) {
        int p1 = hrany[j].x, p = hrany[j].y;
        int w = hrany[j].w;
        dlzka[p][r] = min(dlzka[p][r], w + dlzka[p1][r-1])
    }
}

V tejto časti si môžeme položiť ešte jednu otázku. Vieme, že hodnota \(c \leq m\). Môžeme mať však najkratšiu cestu, ktorá prechádza cez \(m\) hrán? Odpoveď je, že nie. Dokonca nemôžeme mať najkratšiu cestu, ktorá prechádza cez viac ako \(n-1\) hrán. Uvedomme si totiž, že v najkratšej ceste sa nám nikdy neoplatí vrátiť do toho istého vrchola. Ak by sme to spravili, tak by bolo predsa lepšie vynechať tú časť cesty, v ktorej sme sa iba vracali do už predtým navštíveného vrchola a radšej pokračovať ďalej. Každá hrana najkratšej cesty teda musí ísť do nového, ešte nenavštíveného vrchola, a teda môže mať dĺžku najviac \(n-1\). Časová zložitosť nášho programu je teda zatiaľ \(O(nm)\).

Riešenie viacerých otázok

Vyriešili sme prvú časť úlohy, je na čase pridať si späť podmienky, ktoré sme odstránili. Začnime tým, že musíme vyriešiť \(q\) otázok. Ako sme si už spomínali vyššie, najľahší spôsob je proste zopakovať vyššie uvedený proces \(q\) krát. Otázok však môže byť až 1000, čo je pomerne dosť. Naviac si uvedomme, že vyššie uvedený spôsob počítal viac ako len najkratšiu cestu z \(x\) do \(y\).

Vyššie uvedenný program spočítal pre začiatočný vrchol \(x\) najkratšie cesty všetkých dĺžok do všetkých zvyšných vrcholov a uložil ich do poľa dlzka[][]. Ak teda dostaneme dve otázky, ktoré majú rovnaký začiatočný vrchol, neoplatí sa nám toto pole počítať od začiatku, lebo výsledok bude ten istý. Iba sa budeme musieť pozrieť do iných políčok tohto poľa.

Naviac, vrcholov je iba 150, takže túto tabuľku budeme musieť prepočítavať najviac 150 krát. Aj to je však mierne ošemetné. Predsa len si musíme otázky rozdeliť podľa počiatočného vrchola a potom to vo vhodných momentoch prepočítať. Na to sme príliš leniví. Pridajme nášmu poľu teda ešte jeden rozmer. Hodnota dlzka[x][y][r] bude teda dĺžka najkratšej cesty z vrchola \(x\) do vrchola \(y\), ktorá prejde cez práve \(r\) hrán.

Takúto tabuľku si vieme spočítať dopredu v čase \(O(m\cdot n^2)\). Ako z nej však zistíme odpoveď na zadanú otázku? Otázky, ktoré dostávame sa pýtajú na cesty s najviac \(\boldsymbol{c_i}\) hranami. Pre zadané \(a_i\) a \(b_i\) sa teda musíme pozrieť na všetky hodnoty \(dlzka[a_i][b_i][j]\) pre \(0 \leq j \leq c_i\) a vybrať z nich tú najmenšiu. Odpovedanie na jednu otázku by nám teda trvalo čas \(O(n)\).

Vieme to však spraviť aj lepšie. Uvedomme si, že na začiatku si vypočítame celé pole dlzka[][][]. No a správna odpoveď pre \(a_i\), \(b_i\) a \(c_i\) je vždy minimom z hodnôt \(dlzka[a_i][b_i][j]\) (\(0 \leq j \leq c_i\)). Môžeme si tieto minimá preto pre každú dvojicu vrcholov \((a, b)\) vypočítať dopredu. Stojí nás to síce čas \(O(n^3)\), ten sa však ľahko schová do časovej zložitosti \(O(m\cdot n^2)\)¹, ktorou počítame pole dlzka[][][].

Odpoveď na každú otázku vieme teda získať v čase \(O(1)\) jedným pozretím do tabuľky.

Rast váhy hrany na ceste

Ostáva nám vyriešiť poslednú podmienku zadania. Hrany v našich cestách musia postupne rásť.

Pozrime sa najskôr na to, ako funguje naše doterajšie riešenie. Pre zvolený začiatok cesty sa postupne pokúša pridať ďalšie a ďalšie hrany, pričom skúša pridať všetky možné hrany. Vo vzorovom riešení však nemôžeme skúšať všetky hrany. V okamihu ako na nejakej ceste použijeme hranu s váhou \(w\), nemôžeme k tejto ceste pripájať ľahšie hrany. Opačne, ak chceme použiť nejakú hranu s váhou \(w\), môžeme túto hranu pripojiť iba na cestu, ktorá sa skladá z iba ľahších hrán.

Náš algoritmus by sme teda chceli upraviť tak, aby sme v momente, keď pridávame hranu s váhou \(w\), už mali vypočítané všetky cesty z kratších hrán. Naviac aj tieto cesty musia spĺňať podmienku o raste váh hrán. To ale znamená, že hrany musíme spracovávať v poradí od najľahšej po najťažšiu.

Celé riešenie teda vyzerá nasledovne. Usporiadame si hrany podľa váhy. Následne v tomto poradí hrany spracovávame. V každom kroku vyskúšame aktuálnu hranu pripojiť na každú možnú cestu, ktorú zatiaľ máme. Tieto cesty sa pritom dajú reprezentovať pomocou začiatočného vrchola \(x\), koncového vrchola \(y\) a počtu hrán, ktoré obsahujú. V okamihu, keď sme túto hranu vyskúšali pridať na každé miesto, pokračujeme s ďalšou hranou a k tejto sa už nevraciame.

Uvedomme si, že v okamihu keď začneme spracovávať nejakú hranu, máme už vypočítané všetky cesty skladajúce sa z ľahších hrán. Neskôr túto hranu už použiť nemusíme (a nemôžeme), každá nová cesta totiž musela vzniknúť pridaním ťažšej hrany a k tej ju nemôžeme pridať.

Najkrajšie je, že naše riešenie sa ani veľmi nezmení. Jediné čo musíme spraviť je, že presunieme cyklus, ktorý prechádza všetkými hranami, na najvyššiu úroveň. To bude totiž predstavovať to, že hrany spracovávame jednu po druhej.

Časová zložitosť našeho riešenia je \(O(m\log m + m\cdot n^2 + q)\). Pamäťová zložitosť je \(O(n^3)\), keďže si musíme pamätať pole dlzka[][][].

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

#define For(i,n) for(int i=0; i<(n); i++)
#define mp(a,b) make_pair((a),(b))
typedef long long ll;
typedef pair<int,int> pii;

struct hrana {
    int x,y;
    int w;
};

bool cond(hrana a, hrana b) {
    if(a.w < b.w) return true;
    return false;
}

int n,m,q;
int dlzka[160][160][160];
const int INF = 1000000000;

int main() {
    scanf("%d %d %d",&n,&m,&q);
    For(i,160) For(j,160) For(k,160) dlzka[i][j][k]=INF;
    For(i,n) dlzka[i][i][0]=0; // na 0 krokov sa vieme dostat do toho isteho vrchola
    vector<hrana> hrany(m);
    For(i,m) {
        scanf("%d %d %d",&hrany[i].x, &hrany[i].y, &hrany[i].w);
        hrany[i].x--; hrany[i].y--;
    }
    sort(hrany.begin(), hrany.end(), cond);
    For(i, hrany.size()) {
        int x = hrany[i].x, y = hrany[i].y, w = hrany[i].w;
        For(j,n) for(int k = 1; k<n; k++) {
            dlzka[j][y][k] = min(dlzka[j][y][k], w + dlzka[j][x][k-1]);
        }
    }
    // upravim pole dlzka tak, aby obsahovalo vysledky
    For(i,n) For(j,n) for(int k = 1; k < n; k++) {
        dlzka[i][j][k] = min(dlzka[i][j][k], dlzka[i][j][k-1]);
    }
    // odpoviem na otazky
    For(i,q) {
        int x,y,c;
        scanf("%d %d %d",&x,&y,&c);
        x--; y--;
        c = min(c, n-1);
        if(dlzka[x][y][c] == INF) printf("-1\n");
        else printf("%d\n",dlzka[x][y][c]);
    }
}