Array of Vectors amd other STL questions
Hi,
I'm experimenting to code dijkstra with STL. The STL version of the algorithm runs slower than the hand-written heap, expectedly.
Even though STL one probably will never work as fast as the C version with heap, I'm looking for some tips to speed up this code.
here is the code:
Code:
#include <iostream>
#include <cstdio>
#include <set>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <vector>
#include <algorithm>
#include <utility>
//#define ii pair<int,int>
#define MAXV 8002
#define UNDIRECTED 1
#define MAX 0x7fffffff
int startv = 1, finalv = 0, nvertex, nedge;
using namespace std;
FILE *in,*out;
//ifstream in("girdi.in");
void dijkstra();
void read_file();
struct ii {
int first;
int second;
ii(int a,int b) { first = a,second = b; }
};
bool operator<(const ii &a, const ii &b) { return a.first < b.first || (a.first == b.first && a.second < b.second); }
vector<ii > m[MAXV];
int main() {
clock_t start = clock(), end;
read_file();
dijkstra();
end = clock();
printf("sure : %f\n",(float)(end-start)/CLOCKS_PER_SEC);
}
void read_file() {
in = fopen("girdi.in","r");
fscanf(in,"%d%d",&nvertex,&nedge);
finalv = nvertex;
for (int i=0; i<nedge; ++i) {
int v1,v2,w;
fscanf(in,"%d%d%d",&v1,&v2,&w);
m[v1].push_back(ii(v2,w));
if (UNDIRECTED) m[v2].push_back(ii(v1,w));
}
}
void dijkstra() {
set<ii > Q;set<ii >::iterator var;
int d[MAXV]; for (int i=0; i<MAXV; i++) d[i] = MAX;
d[startv] = 0;
Q.insert(ii(startv,d[startv]));
while (!Q.empty()) {
ii cur = *Q.begin();
Q.erase(Q.begin());
int v = cur.first;
for (vector<ii >::iterator it = m[v].begin(); it != m[v].end(); it++) {
int v2 = it->first, cost = it->second;
if (d[v2] > d[v] + cost) {
if (d[v2] != MAX) {
var = Q.find(ii(v2,d[v2]));
if (var != Q.end()) Q.erase(var);
}
d[v2] = d[v] + cost;
Q.insert(ii(v2,d[v2]));
}
}
}
printf("%d\n",d[finalv]);
}
As far as i know, vector allocates some space and if more elements are being added, it doubles its capacity and copies its element into this doubled vector. If I can specify its capacity beforehand(thus decreasing this slow copying process's effect), the code would run faster, I guess. How can I do this?
Besides of this, what else can you suggest to improve the performance of above code?
Thanks in advance