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

Zadanie Bitocja - Algorytm Dijkstry.

VPS Starter Arubacloud
0 głosów
412 wizyt
pytanie zadane 17 czerwca 2022 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 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ź

+1 głos
odpowiedź 18 czerwca 2022 przez Whistleroosh Maniak (56,900 p.)
wybrane 12 lutego 2023 przez pasjonat_algorytmiki
 
Najlepsza
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 18 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
No tak faktycznie muszę to poprawić. Dzięki!
komentarz 19 czerwca 2022 przez Whistleroosh Maniak (56,900 p.)

Możesz próbować to przyspieszyć implementując Dijkstre tak jak tutaj W sensie musisz dodatkowo usuwać niepotrzebne wierzchołki z seta. Wtedy jedna Dijkstra powinna działać w O(nlogn + m). Żeby przyspieszyć sprawdzanie czy dana krawędź zmniejsza odległość 1->n możesz próbować liczyć najmniejsza odległość od 1 do każdego wierzchołka i od n do każdego wierzchołka. Wtedy dodajesz krawędż u -> v jeśli dist(1, u) + dist(u, v) + dist(v, n) (lub na odwrót) zmniejsza odległość.

komentarz 20 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Okej, spróbuję to zamienić. Zmienię też na kolejkę priorytetowa skoro jest trochę szybsza.
komentarz 20 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Napisałem coś takiego:

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

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;
    }
};

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

vector<vector<Krawedz>> krawedzie;

long long dijkstra(int n)
{
    const long long INF = 1000000000;
    priority_queue<Wierzcholek> Q;
    vector<long long> koszt_wierzcholka;
    koszt_wierzcholka.assign(n+1,INF);
    Q.push({0,1});
    koszt_wierzcholka[1] = 0;
    while (!Q.empty())
    {
        Wierzcholek sprawdzany = Q.top();
        Q.pop();
        if (koszt_wierzcholka[sprawdzany.numer_wierzcholka] < sprawdzany.cena)
        {
            continue;
        }
        for (auto edge : krawedzie[sprawdzany.numer_wierzcholka])
        {
            long long to = edge.do_kod;
            long long len = edge.cena;
            if (koszt_wierzcholka[sprawdzany.numer_wierzcholka] +  len < koszt_wierzcholka[to])
            {
                koszt_wierzcholka[to] = koszt_wierzcholka[sprawdzany.numer_wierzcholka] +  len;
                Q.push({koszt_wierzcholka[to],to});
            }
        }
    }
    return  koszt_wierzcholka[n];
}

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";
            krawedzie[a].pop_back();
            krawedzie[b].pop_back();
        }
    }


    return 0;
}

Wydaje mi się, że to powinno działać szybciej niż poprzedni, a więcej testów ma przekroczono limit czasu. Gdzie jest błąd?

komentarz 20 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Wydaje mi się że ten if w 43 linii jest bez sensu jednak, bo tosamo robię w lini 52. Więc go pewnie muszę zmienić.
komentarz 20 czerwca 2022 przez Whistleroosh Maniak (56,900 p.)
Ten if jest potrzebny jeżeli korzystasz z kolejki, bo może być tak że w kolejce jest kilka takich samych wierzchołków, ale różniących się tylką ceną. Wtedy jeżeli odwiedzisz jakiś wierzchołek x to nie ma sensu odwiedzać innych x-ów. Ogólnie wydaję mi się, że set mimo wszystko będzie trochę szybszy. W tym artykule co podlinkowałem jest to nawet napisane. Cieżko mi powiedzieć, czy w tym zadaniu trzeba zoptymalizować tą disjktrę, czy może wymysleć jakiś inny algorytm np. coś z bin searchem
komentarz 20 czerwca 2022 przez Whistleroosh Maniak (56,900 p.)

Mam wersje za 60pkt

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

typedef uint32_t ul;
typedef int32_t l;
typedef uint64_t ull;
typedef int64_t ll;

const l INF = 1000000000 + 9;
const ll MOD = 123456789;
const l PRIME = 200003;
const ll L_INF = 1000000000000000000LL + 7;
const double EPS = 1e-5;

#define FOR(x, y, z) for (l z = x; z < y; z++)
#define FORE(x, y, z) for (l z = x; z <= y; z++)
#define FORD(x, y, z) for (l z = x; z > y; z--)
#define FORDE(x, y, z) for (l z = x; z >= y; z--)
#define REP(x, y) for (l y = 0; y < x; y++)
#define ALL(...) (__VA_ARGS__).begin(), (__VA_ARGS__).end()

#define PF push_front
#define POF pop_front
#define PB push_back
#define POB pop_back
#define MP make_pair
#define FS first
#define SC second
 
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;
    }
};
 
struct Krawedz
{
    long long cena;
    long long do_kod;
};
 
vector<vector<Krawedz>> krawedzie;
vector<long long> koszt_wierzcholka[2];
 
long long dijkstra(int from, int to, int which)
{
    set <Wierzcholek> Q;
    fill(koszt_wierzcholka[which].begin(), koszt_wierzcholka[which].end(), L_INF);
    koszt_wierzcholka[which][from] = 0;

    Q.insert({0,from});

    while (!Q.empty())
    {
        Wierzcholek sprawdzany = *(Q.begin());
        Q.erase(Q.begin());
 
        if (sprawdzany.numer_wierzcholka == to)
            return sprawdzany.cena;

        if (koszt_wierzcholka[which][sprawdzany.numer_wierzcholka] != sprawdzany.cena)
            continue;

        for (auto edge : krawedzie[sprawdzany.numer_wierzcholka])
        {
            long long u = edge.do_kod;
            long long len = edge.cena;
            if (koszt_wierzcholka[which][sprawdzany.numer_wierzcholka] +  len < koszt_wierzcholka[which][u])
            {
                if (koszt_wierzcholka[which][u] != INF)
                    Q.erase({koszt_wierzcholka[which][u], u});
                    
                koszt_wierzcholka[which][u] = koszt_wierzcholka[which][sprawdzany.numer_wierzcholka] +  len;
                Q.insert({koszt_wierzcholka[which][u],u});
            }
        }
    }

    return 1000000000LL;
}
 
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;
    long long wynik = 0;

    cin >> n >> k >> m;

    koszt_wierzcholka[0] = vector<long long>(n+1, L_INF);
    koszt_wierzcholka[1] = vector<long long>(n+1, L_INF);
 
    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});
    }
 
    dijkstra(1, n, 0);
    dijkstra(n, 1, 1);
 
    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 = min(
            koszt_wierzcholka[0][a] + wczytany_koszt + koszt_wierzcholka[1][b],
            koszt_wierzcholka[0][b] + wczytany_koszt + koszt_wierzcholka[1][a]
        );
 
        if (wynik < koszt_wierzcholka[0][n])
        {
            cout << "1 \n";
            dijkstra(1, n, 0);
            dijkstra(n, 1, 1);
        }

        else
        {
            cout << "0 \n";
            krawedzie[a].pop_back();
            krawedzie[b].pop_back();
        }
    }
 
 
    return 0;
}

 

komentarz 20 czerwca 2022 przez Whistleroosh Maniak (56,900 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 20 czerwca 2022 przez Whistleroosh Maniak (56,900 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 20 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 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 20 czerwca 2022 przez Whistleroosh Maniak (56,900 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 20 czerwca 2022 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Dzięki

Podobne pytania

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

92,452 zapytań

141,262 odpowiedzi

319,085 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...