Mam takie zadanie: https://sio2.mimuw.edu.pl/c/zwo22/p/trz/ Wydaje mi się, że treść to zaimplementuj MST, napisałem kod, który się daje wrong answer w wszystkich testach oprócz przykładowego....
Wie ktoś może, gdzie jest błąd, co dziwne kod jest bardzo krótki. Korzystam z mojego ulubionego(wsumie jedynego jakiego znam, ale uznałem, że jest ulubiony bo bardzo lubię algorytm Dijkstry, a on wydaje się być podobny.....) algorytmu do szukania MST - algorytmu Prima.
Kod:
#include <iostream>
#include <vector>
#include <set>
using namespace std;
struct Krawedz
{
int do_kogo;
int cena;
};
struct Element_seta
{
int wierzcholek;
int cena;
bool operator < (const Element_seta &element_seta) const
{
if (cena == element_seta.cena)
return wierzcholek < element_seta.wierzcholek;
return cena < element_seta.cena;
}
};
int n = 0, m = 0, x = 0, y = 0, z = 0, wyn = 0;
vector<vector<Krawedz>> krawedzie;
set<Element_seta> S;
vector<int> dp;
int main()
{
// Algorytm Prima, do wyznaczania MST.
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
dp.assign(n+1,-1);
krawedzie.assign(n+1,{});
for (int i = 0; i < m; ++i)
{
cin >> x >> y >> z;
krawedzie[x].push_back({y,z});
krawedzie[y].push_back({x,z});
}
S.insert({1,0});
dp[1] = 0;
while(!S.empty())
{
Element_seta spr = *S.begin();
S.erase(spr);
wyn += spr.cena;
for (int i = 0; i < krawedzie[spr.wierzcholek].size(); ++i)
{
int wierz = krawedzie[spr.wierzcholek][i].do_kogo;
if (dp[wierz] == -1 or krawedzie[spr.wierzcholek][i].cena < dp[wierz])
{
auto it = S.find({wierz, dp[wierz]});
if (it != S.end())
S.erase(*it);
dp[wierz] = krawedzie[spr.wierzcholek][i].cena;
S.insert({wierz, dp[wierz]});
}
}
}
cout << wyn << '\n';
return 0;
}
Dodam, że w sprawie MST, jestem kompletnym świeżakiem, jest to chyba dopiero drugie zadanie jakie robię na MST, pierwsze to było coś w stylu: zaimplementuj MST.
Z góry dziękuję za pomoc i poświęcony czas!