Thread: Array of Vectors amd other STL questions

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:

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]);
}

the bolds fixed the problem.