Jaką ten algorytm ma złożonność?, Zadanie Zawody 1 etap OI, Algorytm Dijkstry

Question

Natknąłem się na zadanie Zawody z 1 etapu XI OI: https://szkopul.edu.pl/problemset/problem/UiDG8sd_wsS2RfUPL3zQQ1XW/site/?key=statement

Napisałem algorytm, który wydaje mi się, że działa w O(N^2 * lg(N) ), odpalam Dijkstrę z każdego wierzchołka x, do którego wychodzi krawędź z wierzchołka 1 -> x (wierzchołek 1 to wejściowy). Kod wchodził na 70pkt, ale po dodaniu linii 57 i 58(żeby nie iśc niepotrzebnie tą Dijkstrą, jak wynik i tak będzie większy) daje 100pkt z bardzo dużym zapasem. Myślałem, że to poprostu przyśpieszy, ale myślałem, że nie wejdzie na 100, bo dalej jest O(N^2 * lg(N)). Więc zastanawiam się, czy złożonność się amortyzuje do lepszej złożonności, czy poprostu dlatego, że jest tylko 10 testów właściwych + 5 przykładowych(W wszystkich się szybko kończy)? W ksiażce "Przygody Bajtazara 25 lat Olimpiady Informatycznej" jest opisane rozwiązanie O((N+M) * lg(N)), którego jeszcze nie rozumiem, ale tez używają tam Dijkstry. Poglądowy rysunek mojego rozwiązania, jakbym źle opisał. Na czerwono zaznaczone wierzchołki, z których puszczam Dijkstrę(osobno), na zielono jakieś przykładowe wierzchołki z krawędziami(gdzie zwroty to wierzchołki), a wierzchołek "wejsciowy", ma numer 1.

Kod:

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

using namespace std;

struct Krawedz
{
    int do_kogo;
    int waga;
};

struct Element_seta
{
    int wierzcholek;
    int wartosc;
    bool operator < (const Element_seta &element_seta) const
    {
        if (wartosc == element_seta.wartosc)
            return wierzcholek < element_seta.wierzcholek;
        return wartosc < element_seta.wartosc;
    }
};

int n = 0, m = 0, a = 0, b = 0, c = 0, d = 0, wyn = 0, min_wyn = 1e9+20;
vector<vector<Krawedz>> krawedzie;
vector<int> dp;
set<Element_seta> S;

int main()
{
    // O(N^2 * lg(N))???
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    krawedzie.assign(n+1,{});
    dp.assign(n+1,-1);
    for (int i = 0; i < m; ++i)
    {
        cin >> a >> b >> c >> d;
        krawedzie[a].push_back({b,c});
        krawedzie[b].push_back({a,d});
    }

    for (int i = 0; i < krawedzie[1].size(); ++i)
    {
        fill(dp.begin(),dp.end(),-1);
        S.clear();
        dp[krawedzie[1][i].do_kogo] = krawedzie[1][i].waga;
        S.insert({krawedzie[1][i].do_kogo,krawedzie[1][i].waga});
        wyn = -1;
        while(!S.empty())
        {
            Element_seta spr = *S.begin();
            if (spr.wartosc > min_wyn)
                break;
            S.erase(spr);
            if (spr.wierzcholek == 1)
            {
                wyn = spr.wartosc;
                break;
            }
            for (int j = 0; j < krawedzie[spr.wierzcholek].size(); ++j)
            {
                int v = krawedzie[spr.wierzcholek][j].do_kogo;
                if (v == 1 && spr.wierzcholek == krawedzie[1][i].do_kogo)
                    continue;
                if (dp[v] == -1 || spr.wartosc + krawedzie[spr.wierzcholek][j].waga < dp[v])
                {
                    auto it = S.find({v,dp[v]});
                    if (it != S.end())
                        S.erase(*it);
                    dp[v] = spr.wartosc + krawedzie[spr.wierzcholek][j].waga;
                    S.insert({v,spr.wartosc + krawedzie[spr.wierzcholek][j].waga});
                }
            }
        }
        if (wyn != -1)
            min_wyn = min(min_wyn,wyn);
    }

    cout << min_wyn << '\n';

    return 0;
}

Z góry dziękuję za pomoc i poświęcony czas!

Answer 1

Chyba takie coś by się skwadraciło. Dijsktre startujemy z kolejnych wierzchołków od lewej do prawej. Ogólnie dla n <= 5000 złożoność O(n^2logn) nie jest aż taka zła. Powinna wystarczyć żeby zdobyć większość punktów. O ile ktoś specjanie nie da testów z pesymistycznym przypadkiem to dla losowego grafu Twój algorytm powinien chyba całkiem szybko działać. 

Comments

czyli poprostu słabe testy były, które nie wychwyciły tego.