• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Zadanie Bitocja - Algorytm Dijkstry.

0 głosów
60 wizyt
pytanie zadane 17 czerwca w Algorytmy przez pasjonat_algorytmiki Obywatel (1,080 p.)

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!

1 odpowiedź

0 głosów
odpowiedź 6 dni temu przez Whistleroosh Nałogowiec (33,520 p.)
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ć.
komentarz 4 dni temu przez Whistleroosh Nałogowiec (33,520 p.)
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ć
komentarz 4 dni temu przez Whistleroosh Nałogowiec (33,520 p.)
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
komentarz 4 dni temu przez pasjonat_algorytmiki Obywatel (1,080 p.)
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ć.
komentarz 4 dni temu przez Whistleroosh Nałogowiec (33,520 p.)

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 :)

komentarz 4 dni temu przez pasjonat_algorytmiki Obywatel (1,080 p.)
Dzięki

Podobne pytania

0 głosów
0 odpowiedzi 125 wizyt
0 głosów
1 odpowiedź 252 wizyt
pytanie zadane 6 marca 2020 w C i C++ przez Ambitnystudent Nowicjusz (120 p.)
0 głosów
1 odpowiedź 151 wizyt
pytanie zadane 26 grudnia 2019 w C i C++ przez Dawid Penderewski Nowicjusz (120 p.)

88,311 zapytań

136,904 odpowiedzi

305,517 komentarzy

58,593 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...