Array of Vectors amd other STL questions

This is a discussion on Array of Vectors amd other STL questions within the C++ Programming forums, part of the General Programming Boards category; Why not post your corrected code? That way we all can learn too....

  1. #16
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,781
    Why not post your corrected code? That way we all can learn too.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  2. #17
    Registered User
    Join Date
    Jul 2006
    Posts
    25
    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.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. question about multidimensional arrays
    By richdb in forum C Programming
    Replies: 22
    Last Post: 02-26-2006, 08:51 AM
  2. dynamic array of vectors
    By axr0284 in forum C++ Programming
    Replies: 8
    Last Post: 02-25-2006, 11:01 PM
  3. 2 Array questions
    By f97tosc in forum C Programming
    Replies: 2
    Last Post: 03-23-2003, 05:22 PM
  4. Replies: 72
    Last Post: 11-25-2002, 04:55 PM
  5. Hi, could someone help me with arrays?
    By goodn in forum C Programming
    Replies: 20
    Last Post: 10-18-2001, 09:48 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21