برنامه دیکسترا با هیپ( اگه ممکنه یه نگاهی به کد بندازید)

[root88]

سلام، من کد زیر رو تو یه سایت پیدا کردم که اومده دیکسترا رو با هیپ نوشته، اما من نمیفهمم چیکار کرده/ اگه ممکن هست دوستان کد رو توضیح بدن. ممنونم.



#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>

using namespace std;

#define VMAX (1001)
#define EMAX (30001)
#define INTMAX (9223372036854775807LL)

ifstream fin("dij.in");
ofstream fout("dij.out");

int visited[VMAX];
vector< pair<long long,int> > adjlist[VMAX];
vector< pair<long long,int> > priolist; //distance list will be a heap now

int main()
{
int V,E;

fin >> V; fin >> E;

for(int i=0; i<E; i++) {
int v1,v2,tmp;
fin >> v1; fin >> v2;
fin >> tmp;
adjlist[v1].push_back(pair<long long, int>(tmp,v2));
adjlist[v2].push_back(pair<long long, int>(tmp,v1));
}

//the distance list is set up as usual
priolist.push_back(pair<long long, int>(0LL,1));

//pulling the minimum off is auotmatically covered by the heap
while(!priolist.empty()) {
int cur=priolist[0].second; //min resides on front
int curdist=priolist[0].first;

//pop_heap takes the head of the heap and puts it on the
//end of the vector, then we take it off.
//also we use greater to make a min heap (default heap is max)
pop_heap(priolist.begin(),priolist.end(),\
greater< pair<long long, int> >());
priolist.pop_back();

//if we hit the desired node, stop.
//also some nodes can come off the heap twice
if(cur==V){fout << curdist << endl; break;}
if(visited[cur]!=0){continue;}

visited[cur]=1;

//this is where some nodes get on the heap more than once
//we allow this because it is more expensive to find and update
//a node once it is on the heap than it is to allow the heap
//to contain more than one possible distance to a node
for(int i=0; i<adjlist[cur].size(); i++) {
if(visited[adjlist[cur][i].second]==0) {
//first we put the desired item on the back of
//the vector for heaping
priolist.push_back(pair<long long,int>(curdist\
+adjlist[cur][i].first,adjlist[cur][i].second));
//then we do the heaping
push_heap(priolist.begin(),priolist.end(),\
greater< pair<long long, int> >());
}
}
}

exit(0);
}