Wydaje mi sie, ze wszystko dobrze zrobilem. Czemu juz po kompilacji w srodku programu wywala mi blad invalid heap?
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <fstream>
#include <time.h>
using namespace std;
struct sasiad
{
int v;
int odleglosc;
};
struct wierzcholek
{
int v; //Numer wierzcholka
sasiad odleglosc[100]; //Tablica sasiadow
int poprzednik; //Numer elementu poprzedniego
int odlegloscodpoczatku; //Odleglosc od poczatkowego wierzcholka
bool zdjetyzkopca; //Czy wierzcholek byl juz na kopcu
};
vector <wierzcholek> dane;
int n;
const int nieskonczonosc=5000;
class cmp
{
public:
bool operator() (const wierzcholek& a, const wierzcholek& b)
{
return a.odlegloscodpoczatku>b.odlegloscodpoczatku;
}
};
void wypisz()
{
for (unsigned int i=0; i<dane.size();++i)
{
cout<<dane[i].odlegloscodpoczatku<<"\n";
}
}
void Dijkstra(int pocz)
{
cmp porownywarka;
for (unsigned int i=0; i<dane.size();++i)
{
dane[i].odlegloscodpoczatku=nieskonczonosc;
dane[i].poprzednik=0;
dane[i].zdjetyzkopca=false;
}
dane[pocz].odlegloscodpoczatku=0;
wypisz();
cout<<endl;
wierzcholek u;
int v; //sasiad
make_heap(dane.begin(), dane.end(), porownywarka);
unsigned int rozmiarkopca=dane.size(); //NA POCZATKU SA NAJMNIEJSZE !
vector <wierzcholek>::iterator it=dane.end();
while (rozmiarkopca!=0)
{
//make_heap(dane.begin(), dane.end(), porownywarka);
u=dane.front();
pop_heap(dane.begin(), it, porownywarka); //SKURWIA NA KONIEC
//dane.pop_back();
for (unsigned int i=0; u.odleglosc[i].v; ++i) //Dla wszystkich sasiadow
{
for (int j=0; ;j++)
if (u.odleglosc[i].v==dane[j].v)
{
v=j;
break;
}
if (dane[v].odlegloscodpoczatku>u.odlegloscodpoczatku+u.odleglosc[i].odleglosc)
{
dane[v].odlegloscodpoczatku=u.odlegloscodpoczatku+u.odleglosc[i].odleglosc;
dane[v].poprzednik=u.v;
}
}
dane.push_back(u);
--rozmiarkopca;
it=dane.end()-rozmiarkopca;
wypisz();
cout<<endl<<rozmiarkopca<<endl<<endl;
}
}
int main()
{
ifstream wej("In0403.txt");
ofstream wyj("Out0403.txt");
int warszawa;
char linia[257];
wej>>n;
dane.resize(n);
wej>>warszawa;
warszawa -=1;
wej.get();
int k=0;
for (int i=0; i<n; ++i)
{
wej.getline(linia, 256);
k=0;
for (int j=4; linia[j]!=0; ++j)
{
if (isdigit(linia[j]))
{
dane[i].v=i+1;
dane[i].odleglosc[k].v=atoi(linia+j);
dane[i].odleglosc[k].odleglosc=atoi(linia+j+2);
++k;
}
if (*(linia+j+4))
j=j+4;
else break;
}
}
Dijkstra(warszawa);
wypisz();
wej.close();
wyj.close();
return 0;
}
Sam algorytm to : http://pl.wikipedia.org/wiki/Algorytm_Dijkstry
Tresc zadania i format danych wejsciowych tutaj : http://www.zp89.republika.pl/SEM_3/ASD/Borowska_Listy_zadan/04.jpg - zadanie 3