Why not post your corrected code? That way we all can learn too.
Printable View
Why not post your corrected code? That way we all can learn too.
the main problem of mine was that, i put the items in the set, and the way i put sorted the items according to their node number, instead of the cost. some little modifications corrected the code. here is the corrected code:
the bolds fixed the problem.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() {
read_file();
clock_t start = clock(), end;
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<MAXV; i++) m[i].reserve(100);
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(d[startv],startv));
while (!Q.empty()) {
ii cur = *Q.begin();
Q.erase(Q.begin());
int v = cur.second;
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(d[v2],v2));
if (var != Q.end()) Q.erase(var);
}
d[v2] = d[v] + cost;
Q.insert(ii(d[v2],v2));
}
}
}
printf("%d\n",d[nvertex]);
}