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!