Zadanie Bitocja - Algorytm Dijkstry.

Question

Cześć,

Ostatnio natknąłem się na zadanie z 3 etapu 1 edycji OIG - https://szkopul.edu.pl/problemset/problem/HP0-iQt7v7vElza8XxoucKto/site/?key=statement

Wydaje mi się, że mam dobry pomysł a mianowicie: Robię algorytm Dijkstry najpierw dla danych krawędzi które mamy i ustalam min wynik, potem dodaję cały czas kolejną krawędź i sprawdzam znowu algorytmem Dijkstry czy wynik się nie poprawił jak tak to wypisuję 1 w przeciwnym razie 0.

Dostaję jednak tylko 20 pkt (19 testów łącznie - 7 dobrze,5 zle odpowiedzi, 7 przekroczono limit czasu). Pewnie dlatego, że mam jakiś błąd w algorytmie Dijkstry. (Pierwszy raz piszę ten algorytm) Nie mogę znaleźć błędu. Wyczytałem w internecie, że najszybsza wersja tego algorytmu to na kolejce priorytetowej, więc set też powinien być ok. Jak ktoś by znajdzie błąd to jestem bardzo wdzięczny. Kod: 

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Wierzcholek
{
    long long cena;
    long long numer_wierzcholka;

    bool operator < (const Wierzcholek&wierzcholek) const
    {
        if (cena != wierzcholek.cena)
        {
            return cena < wierzcholek.cena;
        }
        return numer_wierzcholka > wierzcholek.numer_wierzcholka;
    }

    bool operator == (const Wierzcholek&wierzcholek) const
    {
        return numer_wierzcholka == wierzcholek.numer_wierzcholka;
    }
};

struct Krawedz
{
    long long cena;
    long long do_kod;
};

vector<vector<Krawedz>> krawedzie;

long long dijkstra(int n)
{
    set <Wierzcholek> Q;
    vector<bool> czy_odwiedzony;
    for (int i = 0 ; i <= n; ++i)
    {
        czy_odwiedzony.push_back(false);
    }
    Q.insert({0,1});
    while (!Q.empty())
    {
        Wierzcholek sprawdzany;
        for (auto c : Q)
        {
            sprawdzany = c;
            break;
        }

        if (sprawdzany.numer_wierzcholka == n)
        {
            return sprawdzany.cena;
        }
        czy_odwiedzony[sprawdzany.numer_wierzcholka] = true;

        for (int i = 0; i < krawedzie[sprawdzany.numer_wierzcholka].size(); ++i)
        {
            if (czy_odwiedzony[krawedzie[sprawdzany.numer_wierzcholka][i].do_kod] == false)
            {
                Q.insert({sprawdzany.cena + krawedzie[sprawdzany.numer_wierzcholka][i].cena,krawedzie[sprawdzany.numer_wierzcholka][i].do_kod});
            }
        }
        Q.erase(sprawdzany);
    }
}

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

    int n = 0, k = 0, m = 0, a = 0, b = 0, wczytany_koszt = 0, min_wynik = 0, wynik = 0;

    cin >> n >> k >> m;

    for (int i = 0 ; i <= n; ++i)
    {
        krawedzie.push_back({});
    }

    for (int i = 0; i < k; ++i)
    {
        cin >> a >> b >> wczytany_koszt;
        krawedzie[a].push_back({wczytany_koszt,b});
        krawedzie[b].push_back({wczytany_koszt,a});
    }

    min_wynik = dijkstra(n);

    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b >> wczytany_koszt;
        krawedzie[a].push_back({wczytany_koszt,b});
        krawedzie[b].push_back({wczytany_koszt,a});

        wynik = dijkstra(n);

        if (wynik < min_wynik)
        {
            cout << "1 \n";
            min_wynik = wynik;
        }
        else
        {
            cout << "0 \n";
        }
    }


    return 0;
}

Czy wogóle poprawnie piszę ten algorytm ? W sensie żeby była najszybsza wersja.

Z góry bardzo dziękuję za pomoc!

Answer 1

W else w linii 107 powinieneś usunąc dodane drogi. One mają być wybudowane tylko wtedy, gdy skracają długość trasy 1->n.

Jeżeli chodzi o Dijsktre to jedyna zmiana jaką bym polecił to żeby nie wchodzić do wcześniej odwiedzonego wierzchołka. W ifie w 61. linii możesz też sprawdzać czy opłaca się w ogóle dodawać nowy element do kolejki. A opłaca się dodawać jeśli obliczona odległość jest mniejsza od wszystkich wcześniejszych odległości dla wierzchołka, który próbujesz dodać do kolejki.

Jak poprawisz te rzeczy to nie powinno już być WA, ale wciąż jest TLE. Więc trzeba jeszcze pomysleć co z tym zrobić.

Comments

Udało mi się znaleźć omówienie rozwiązania: https://www.oi.edu.pl/old/html/zadania/oig1/Etap3/bit.pdf Wgl nie pomyślałem, żeby skorzystać z Floyda, bo on akurat rzadko się przydaje przez kiepską złożóność. Ale tutaj przecież jest n < 100, więc Floyd może nawet wystarczyć

---

Ale co ciekawe ich rozwiazanie działa w O(n^3 + n^2m) a nasze w O(nmlogn + m^2), więc dla ograniczeń z zadania powinno wyjść na to samo. A jednak ich jest szybszy

---

Ciekawe, myślałem że pod Olimpiade wystarcza algorytm Dijkstry a tu prosze...

Nigdy nie spotkałem się z algorytmem Floyda, więc muszę się go nauczyć.

---

Do OI to trzeba znać bardzo wiele algorytmów. Ogólnie najlepiej nauczyć się wszystkich algorytm stąd. Jak będziesz miał szczęście to może pojawi się zadanie, którego rozwiązanie jest już na tamtej stronie, bo tak się już zdarzało :)

---

Dzięki