7. Lamborghini? Bicykel! (vzorové riešenie) - Korešpondenčný seminár z programovania

Zadanie

22.02.2022, Amsterdam.

Presne pred rokom Kolektív Sofistikovaných Pesimistov získal 90%-nú väčšinu Klimatizovaného Svetového Parlamentu.

Dnes organizuje tajnú Konferenciu o Sprevinilej Planéte, ktorej cieľom je rozhodnúť o osude našej modrej planéty Zem. Iniciatíva na zvolanie tejto tajnej konferencie bola podaná po zverejnení virálnej eseje šéfa zmieneného kolektívu, Dr. Michala Anderleho, s názvom “Ľudstvo, ktoré si zvolilo pesimistov, stráca nárok na budúcnosť”. Logicky, v kolektíve teraz prevláda názor, že Zem treba odpáliť do vesmíru a/alebo zrovnať so zemou.

Je tu však nádej. Posledný optimista. Posledný pravý optimista, s vôľou zachrániť túto planétu pred nenávratnou skazou. Jeho meno je Askar.

vŕŕŕŕŕ Somebody once told me vŕŕŕŕŕ the world is gonna roll me vŕŕŕŕŕ

Askar:	Haló?
???:	Askar, to som ja, Afrodita.
Askar:	???
Afrodita:	Kolektív Sofistikovaných Pesimistov pripravuje plán na zničenie planéty. Nemôžeš to dopustiť. Na svete je toľko krásy. Musíš okamžite ísť na Konferenciu o Sprevinilej Planéte!
Askar:	To dnes nestíham – myš mi rozhrýzla pneumatiku na mojom Lamborghini.
Afrodita:	Použi miestny bike-sharing systém. Stihneš to.
Askar:	Ale počúvaj… hééj, ty si to zložila? Do kelu aj s tebou!

Úloha

Askar sa musí dostať zo svojho domu na Konferenciu o Sprevinilej Planéte a spraviť tam niečo bombové.

Mapa mesta je neorientovaný graf s \(n\) vrcholmi, očíslovanými \(1, 2, \dots, n\). Vo vrchole \(1\) je Askarov dom a vo vrchole \(n\) sa organizuje konferencia. V niektorých vrcholoch sa nachádzajú bike-sharing stanice. V nich je možnosť nasadnúť na bicykel, alebo ho odložiť a pokračovať pešo. Nikde inde nemožno získať ani odložiť bicykel.

Keď sa Askar hýbe pešo, po jednej hrane prejde za \(k\) minút. Na bicykli to zvláda za \(1\) minútu. Doma bicykel nemá a do budovy konferencie tiež nemôže prísť s bicyklom.

Zistite, koľko minút mu bude trvať, kým dostane šancu zachrániť našú krásnu planétu.

Formát vstupu

Na prvom riadku sa nachádzajú dve kladné celé čísla \(n\) a \(k\) – počet vrcholov grafu a čas, ktorý Askarovi trvá prejdenie jednej hrany pešo.

Na druhom riadku sa nachádza jedno celé číslo \(m\) – počet hrán v grafe.

Každý z nasledujúcich \(m\) riadkov obsahuje dve čísla: \(a_i\), \(b_i\) (\(1 \leq a_i, b_i \leq n\)), ktoré hovoria, že medzi vrcholmi \(a_i\) a \(b_i\) je hrana. Medzi každou dvojicou vrcholov je najviac jedna hrana. Môžete predpokladať, že zo štartu sa dá dostať do každého iného vrcholu postupnosťou hrán.

Na ďalšom riadku je jedno celé číslo \(s\) – počet bike-sharing staníc.

Každý z nasledujúcich \(s\) riadkov obsahuje jedno číslo \(s_i\), ktoré hovorí, že vo vrchole \(s_i\) sa nachádza stanica. Tieto čísla sú rôzne a platí \(1 < s_i < n\).

Formát výstupu

Vypíšte jeden riadok a na ňom jedno číslo – najmenší počet minút, za ktorý sa Askar vie dostať z domu do budovy konferencie.

Hodnotenie

Sú štyri sady vstupov. Platí pre ne nasledovné:

číslo sady	\(1\)	\(2\)	\(3\)	\(4\)
\(n,m\leq\)	\(50\,000\)	\(100\,000\)	\(100\,000\)	\(250\,000\)
\(s \leq\)	\(2\)	\(20\)	\(n-2\)	\(n-2\)

Vo všetkých vstupoch \(1 < k \leq 10^5\). Navyše, pri práci s časovými a pamäťovými zložitosťami môžete predpokladať, že \(O(k) = O(n)\).

Príklad

Input:

Output:

Askar najprv prejde za desať minút hranu do vrcholu \(2\). Vo vrchole \(2\) nasadne na bicykel. Za tri minúty to odbicykluje do vrcholu \(4\), kde bicykel nechá a za ďalších desať minút už dorazí na miesto konferencie.

Každému skúsenému riešiteľovi pravdepodobne napadlo neoptimálne riešenie tejto úlohy hneď po prečítaní zadania. K optimálnemu riešeniu potom už ostáva si len uvedomiť jednu skutočnosť a je to tam.

Poďme sa pozrieť na obe riešenia.

Neoptimálne riešenie – Dijkstra

Askar sa musí dostať zo svojho domu do budovy Konferencie o Sprevinilej Planéte, čo najrýchlejšou cestou. Najznámejším algoritmom na hľadanie najrýchlejšej cesty je starý dobrý Dijkstra. Tu si o ňom môžete prečítať.

V našom prípade ho však nemôžeme aplikovať úplne priamočiaro – Askar môže totiž ísť pešo aj na bicykli. Tento problém sa dá ľahko vyriešiť: pôvodný graf si trochu prerobíme. Každý vrchol \(i\) nahradíme dvoma vrcholmi: \(i_p\) (pešo) a \(i_b\) (bicykel). Vrchol \(i_b\) reprezentuje situáciu, keď je Askar vo vrchole \(i\) a má so sebou bicykel, vrchol \(i_p\) zasa situáciu, keď je Askar vo vrchole \(i\) bez bicykla. Ak v pôvodnom grafe bola hrana medzi vrcholmi \(i\) a \(j\), tak v novom grafe bude hrana \(i_p - j_p\) s dĺžkou \(k\) a hrana \(i_b - j_b\) s dĺžkou \(1\). Čiže, ak bol Askar pešo, tak môže pešo prejsť do druhého vrcholu a podobne, ak bol na bicykli, tak na ňom môže pokračovať. V prípade, že vrchol \(i\) je bike-sharing stanica, tak pridáme ešte dve ďalšie hrany: \(i_p - j_b\) s dĺžkou \(1\) (Askar po tejto hrane už prejde na bicykli) a \(i_b - j_p\) s dĺžkou \(k\) (Askar zosadol z bicykla a túto hranu prejde pešo).

Takto upravený graf má \(2n\) vrcholov a nanajvýš \(6m\) hrán (v najhoršom prípade, ak by skoro všade boli bike-sharing stanice, budeme mať šesť hrán za každú pôvodnú hranu).

V skutočnej implementácii nemusíme ani konštruovať nový graf. Stačí si v halde okrem čísla vrcholu pamätať aj to, či je Askar pešo alebo na bicykli a podľa toho akumulovať vzdialenosti.

Časová zložitosť tohoto riešenia je \(O(m \log m)\) a pamäťová \(O(n + m)\).

#include <bits/stdc++.h>

using namespace std;

struct dijkstra
{
    int stav,vrchol;
    long long cena;
};

struct cmp
{
    bool operator()(const dijkstra&a,const dijkstra&b) const
    {
        return a.cena > b.cena;
    }
};

vector<bool> bicykel;
vector<vector<int> > graf;
vector<long long> dist[2];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

    int n,coef,m;
    cin >> n >> coef >> m;

    graf.resize(n);

    while(m--)
    {
        int x,y;
        cin >> x >> y;
        --x,--y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    bicykel.resize(n,false);
    int b;
    cin >> b;
    while(b--)
    {
        int c;
        cin >> c;
        bicykel[c-1] = true;
    }

    for(int i=0;i<2;++i)
        dist[i].resize(n,(long long)n*coef);

    dist[0][0] = 0;
    priority_queue<dijkstra,vector<dijkstra>,cmp> pq;

    pq.push({0,0,0});

    while(!pq.empty())
    {
        dijkstra d = pq.top();
        pq.pop();
        if(dist[d.stav][d.vrchol] < d.cena) continue;

        for(int i=0;i<graf[d.vrchol].size();++i)
        {
            int kam = graf[d.vrchol][i];
            long long nova_cena = d.cena + 1 + (coef-1)*(d.stav==false);

            if(dist[d.stav][kam] > nova_cena)
            {
                dist[d.stav][kam] = nova_cena;
                pq.push({d.stav,kam,nova_cena});
            }
        }

        if(bicykel[d.vrchol])
        {
            bool novy_stav = !d.stav;
            if(dist[novy_stav][d.vrchol] > d.cena)
            {
                dist[novy_stav][d.vrchol] = d.cena;
                pq.push({novy_stav,d.vrchol,d.cena});
            }
        }
    }

    cout << dist[0][n-1] << "\n";
}

Optimálne riešenie

Intuícia nám napovedá, že predchádzajúce riešenie nie je optimálne. Dijkstra funguje na hocijaké grafy, ale náš graf nie je hocijaký: všetky jeho hrany sú dĺžky \(1\) alebo \(k\). Toto sa musí dať využiť.

A naozaj to ide. Všeobecnú logaritmickú haldu z predchádzajúceho riešenia vieme nahradiť dvoma frontami. Do prvej fronty budeme vkladať vrcholy, keď je Askar na bicykli a do druhej keď je pešo. Ako si o chvíľu ukážeme, obe fronty ostanú vždy usporiadané podľa vzdialenosti, a teda keď chceme vybrať nasledujúci najbližší vrchol (tak, ako to robíme v Dijkstrovi), stačí nám vybrať menší (bližší) z vrcholov na začiatku oboch front.

Tak ako sme si už povedali, obe fronty musia vždy ostať usporiadané, aby naše riešenie fungovalo – inak by sme sa nevedeli spoľahnúť, že nasledujúci vrchol sa nachádza na začiatku niektorej z nich. Dôkaz je veľmi ľahký. Predpokladajme, že doteraz sú fronty usporiadané. Z dvoch začiatkov teda vyberieme menší vrchol, povedzme, že tento vrchol je vo vzdialenosti \(15\). V prípade, že z neho ideme pokračovať peši, do fronty pre pešie vrcholy vložíme vrchol so vzdialenosťou \(15+k\). Aby fronta ostala usporiadaná, nesmel sa v nej nachádzať žiaden vzdialenejší vrchol. Mohol sa? Nemohol: keďže Dijkstrov algoritmus navštivuje vrcholy podľa vzdialenosti (a doteraz boli fronty usporiadané, takže bežal korektne), všetky vrcholy, ktoré sme doteraz navštívili, boli vo vzdialenosti \(15\) alebo menšej. Najvzdialenejší vrchol, ktorý sme doteraz mohli do pešej fronty pridať, mohol mať vzdialenosť najviac \(15 + k\), čo nie je viac, než náš naposledy pridaný vrchol. Fronta teda ostane usporiadaná. Dôkaz pre druhú frontu je úplne rovnaký.

Fronty nám pomohli vyhnúť sa logaritmu, časová zložitosť tohoto riešenia je teda \(O(n + m + s) = O(m)\) a pamäťová je rovnaká. Keďže na vyriešenie úlohy určite musíme minimálne načítať vstup, lepšiu asymptotickú časovú zložitosť sa už dosiahnuť nedá.

#include <bits/stdc++.h>

using namespace std;

struct dijkstra
{
    int stav,vrchol;
    long long cena;
};

vector<bool> bicykel;
vector<vector<int> > graf;
vector<long long> dist[2];

queue<dijkstra> q[2];

bool qempty()
{
    return q[0].empty() && q[1].empty();
}

dijkstra qtop()
{
    if(q[0].empty() || q[1].empty())
    {
        int i = q[0].empty();
        return q[i].front();
    }

    int i = (q[0].front().cena > q[1].front().cena);
    return q[i].front();
}

void qpop()
{
    if(q[0].empty() || q[1].empty())
    {
        int i = q[0].empty();
        q[i].pop();
        return;
    }

    int i = (q[0].front().cena > q[1].front().cena);
    q[i].pop();
}

void qpush(dijkstra d,int i)
{
    q[i].push(d);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

    int n,coef,m;
    cin >> n >> coef >> m;

    graf.resize(n);

    while(m--)
    {
        int x,y;
        cin >> x >> y;
        --x,--y;
        graf[x].push_back(y);
        graf[y].push_back(x);
    }

    bicykel.resize(n,false);
    int b;
    cin >> b;
    while(b--)
    {
        int c;
        cin >> c;
        bicykel[c-1] = true;
    }

    for(int i=0;i<2;++i)
        dist[i].resize(n,(long long)n*coef);

    dist[0][0] = 0;

    qpush({0,0,0},0);

    while(!qempty())
    {
        dijkstra d = qtop();
        qpop();
        if(dist[d.stav][d.vrchol] < d.cena) continue;

        for(int i=0;i<graf[d.vrchol].size();++i)
        {
            int kam = graf[d.vrchol][i];
            long long nova_cena = d.cena + 1 + (coef-1)*(d.stav==false);

            if(dist[d.stav][kam] > nova_cena)
            {
                dist[d.stav][kam] = nova_cena;
                qpush({d.stav,kam,nova_cena},d.stav);
            }
        }

        if(bicykel[d.vrchol])
        {
            bool novy_stav = !d.stav;
            if(dist[novy_stav][d.vrchol] > d.cena)
            {
                dist[novy_stav][d.vrchol] = d.cena;
                qpush({novy_stav,d.vrchol,d.cena},novy_stav);
            }
        }
    }

    cout << dist[0][n-1] << "\n";
}

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ť.

7. Lamborghini? Bicykel! vzorové riešenie