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
    23,630
    Why not post your corrected code? That way we all can learn too.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    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