mercredi 5 avril 2017

Traverse vector

I found an implementation of Bellman-Ford algorithm for finding shortest path to every other node from a source node. The following code snippet uses C++11 auto keyword.

Here e[] is an array containing distances to all nodes, v is adjacency list.

   vector<pair<int,int>> v[N]; // (x,w):edge to node x with weight w
   for (int i = 1; i <= n; i++) 
    {
       e[i] = 1e9;
    }
    e[x] = 0;
    for (int i = 1; i <= n-1; i++) {
        for (int a = 1; a <= n; a++) {
            for (auto b : v[a]) {
                e[b.first] = min(e[b.first],e[a]+b.second);
            }
        }
    }

So I tried to code the same for C++ 4.3 compiler (Don't ask me why) in the following way. Here n is total nodes and m is total edges.

vector<pair<int,int> > adj;
int E[MAXK];
int n,m;
void bellman(int src)
{
    E[src] = 0;
    for(int i=1;i<=n-1;i++)
    {
        for(int a=1;a<=n;a++)a
        {
            for(int b=0;b<adj[a].size();b++)
            {
                E[ adj[a][b].first ] = min( E[adj[a][b].first], E[a] + adj[a][b].second );
            }
        }
    }
}

And I get the following errors -

||=== Build: Debug in hackerearth (compiler: GNU GCC Compiler) ===|
G:\practice\codeforces\hackerearth\hackerearth.cpp||In function 'void bellman(int)':|
G:\practice\codeforces\hackerearth\hackerearth.cpp|47|error: 'struct std::pair<int, int>' has no member named 'size'|
G:\practice\codeforces\hackerearth\hackerearth.cpp|49|error: no match for 'operator[]' in 'adj.std::vector<_Tp, _Alloc>::operator[]<std::pair<int, int>, std::allocator<std::pair<int, int> > >(((std::vector<std::pair<int, int> >::size_type)a))[b]'|
G:\practice\codeforces\hackerearth\hackerearth.cpp|49|error: no match for 'operator[]' in 'adj.std::vector<_Tp, _Alloc>::operator[]<std::pair<int, int>, std::allocator<std::pair<int, int> > >(((std::vector<std::pair<int, int> >::size_type)a))[b]'|
G:\practice\codeforces\hackerearth\hackerearth.cpp|49|error: no match for 'operator[]' in 'adj.std::vector<_Tp, _Alloc>::operator[]<std::pair<int, int>, std::allocator<std::pair<int, int> > >(((std::vector<std::pair<int, int> >::size_type)a))[b]'|
G:\practice\codeforces\hackerearth\hackerearth.cpp||In function 'int main()':|
G:\practice\codeforces\hackerearth\hackerearth.cpp|65|error: 'struct std::pair<int, int>' has no member named 'clear'|
G:\practice\codeforces\hackerearth\hackerearth.cpp|70|error: 'struct std::pair<int, int>' has no member named 'push_back'|
G:\practice\codeforces\hackerearth\hackerearth.cpp|70|warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]|
G:\practice\codeforces\hackerearth\hackerearth.cpp|71|error: 'struct std::pair<int, int>' has no member named 'push_back'|
G:\practice\codeforces\hackerearth\hackerearth.cpp|71|warning: extended initializer lists only available with -std=c++11 or -std=gnu++11 [enabled by default]|
G:\practice\codeforces\hackerearth\hackerearth.cpp|74|error: 'dfs' was not declared in this scope|
||=== Build failed: 8 error(s), 2 warning(s) (0 minute(s), 2 second(s)) ===|

So can you please help me with the code implementation. Thank you.

Aucun commentaire:

Enregistrer un commentaire