UVa Online Judge Runtime Error C++ (341 - Non-Stop Travel)

Question

I have been trying to do the 341 Non-Stop Travel Problem on the UVa Judge Online, but when I submit my code, the judge says that there is a Runtime Error(RE) and I can't detect it. I solved the problem using the Dijkstra Algorithm and adjacency list graph. When I have tested the input example, my program works fine, but I don't know what to do to skip this Runtime error! My code below

#include <iostream>
#include <vector>
#include <list>

#define INFINITY 9999999
#define NIL -1

using namespace std;

class Dijkstra;
class Arc;
class Vertex;
class Graph;

class Arc
{
public:
    int src;
    int dst;
    int weight;

    Arc (int _src, int _dst, int _weight)
    {
        src = _src;
        dst = _dst;
        weight = _weight;
    }

    ~Arc ()
    {

    }
};

class Vertex
{
public:
    vector<Arc*> arcs;
    Vertex ()
    {
        arcs = vector<Arc*>();
    }

    ~Vertex ()
    {
        for (int i = 0; i < (int) arcs.size(); i++)
        {
            delete arcs[i];
        }
    }
};

class Graph
{
public:
    vector<Vertex*> vertices;
    Graph()
    {
        vertices = vector<Vertex*>();
    }

    void addVertex ()
    {
        Vertex* v = new Vertex();
        vertices.push_back(v);
    }

    void addArc(int _src, int _dst, int _weight)
    {
        Arc* a = new Arc(_src,_dst, _weight);
        vertices[_src]->arcs.push_back(a);
    }

    int w(int u, int v)
    {
        for (int i = 0; i < (int) vertices[u]->arcs.size(); i++)
        {
            if (vertices[u]->arcs[i]->dst == v)
            {
                return vertices[u]->arcs[i]->weight;
            }
        }
        return INFINITY;
    }

    void printGraph()
    {
        for (int i = 0; i < (int) vertices.size(); i++)
        {
            for (int j = 0; j < (int) vertices[i]->arcs.size(); j++)
            {
                cout << i+1 << " " << vertices[i]->arcs[j]->dst+1 << " " << vertices[i]->arcs[j]->weight << "\t";
            }
            cout << endl;
        }
    }

    ~Graph ()
    {
        for (int i = 0; i < (int) vertices.size(); i++)
        {
            vertices[i]->~Vertex();
            delete vertices[i];
        }
    }

};


class Dijkstra
{
public:
    int* d;
    int* pi;
    list<int> Q;

    Dijkstra()
    {

    }

    void shortest_paths(Graph* G, int s)
    {
        initialize(G,s);
        Q = addVertices(G);
        while (Q.size() != 0)
        {
            int u = extractCheapest(Q);
            Q.remove(u);
            if (d[u] == INFINITY)
            {
                break;
            }
            for (int i = 0; i < (int) G->vertices[u]->arcs.size(); i++)
            {
                int v = G->vertices[u]->arcs[i]->dst;
                relax(G,u,v);
            }
        }
    }


    void initialize(Graph* G, int s)
    {
        int size = G->vertices.size();
        d = new int[size];
        pi = new int[size];
        for (int i = 0; i < size; i++)
        {
            d[i] = INFINITY;
            pi[i] = NIL;
        }
        d[s] = 0;
    }

    void relax(Graph* G, int u, int v)
    {
        int w = (d[u] + G->w(u,v));
        if (d[v] > w)
        {
            d[v] = w;
            pi[v] = u;
        }
    }

    list<int> addVertices(Graph* G)
    {
        list<int> q;
        for (int i = 0; i < (int) G->vertices.size(); i++)
        {
            q.push_back(i);
        }
        return q;
    }

    int extractCheapest(list<int> Q)
    {
        int minorDist = INFINITY;
        int minorVertex = NIL;
        list<int>::iterator it;
        for (it = Q.begin(); it != Q.end(); it++)
        {
            int dist = d[(*it)];
            if ( dist < minorDist )
            {
                minorDist = dist;
                minorVertex = (*it);
            }
        }
        return minorVertex;
    }

    void printOutput (int cnt, int _d)
    {
        cout << "Case " << cnt << ": Path = ";
        printRecursive(_d);
        cout << "; ";
        cout << d[_d] <<" second delay" << endl;
    }

    void printRecursive(int _d)
    {
        if(pi[_d] == NIL)
        {
            cout << " " << _d + 1;
        }
        else
        {
            printRecursive(pi[_d]);
            cout << " "<< _d + 1;
        }
    }

    ~Dijkstra()
    {
        delete[] d;
        delete[] pi;
    }

};

int main ()
{
    int NI;         
    int NE;          
    int weight;    
    int v;         
    int s;         
    int d;          
    int cnt = 0;

    while (cin >> NI)
    {
        cnt++;
        if (NI !=0 )
        {
            Graph* G = new Graph();
            for (int u = 0; u < NI; u++)
            {
                G->addVertex();
                cin >> NE;
                for (int j = 0; j < NE; j++)
                {
                    cin >> v;
                    cin >> weight;
                    G->addArc(u,v-1,weight);
                }
            }
            cin >> s;
            cin >> d;
            Dijkstra* dijkstra = new Dijkstra();
            dijkstra->shortest_paths(G,s-1);
            dijkstra->printOutput(cnt,d-1);
            G->~Graph();
            dijkstra->~Dijkstra();
        }
    }
    return 0;
}

-------------------------------EDIT-----------------------------
I have made things in the code to avoid the Runtime Error. First I corrected my mistakes of memory leak (Thanks us2012 and NPE!) then I treated cases of disconnected graphs. This is the version of the code that was accepted by the judge.

Answer 1

The problem is here:

        vertices[i]->~Vertex();
        delete vertices[i];

The destructor is called automatically when you delete it, so essentially you're calling it twice. This is how you find out about that when you don't know it: (relevant lines marked as "HERE:")

$ valgrind --tool=memcheck ./program341
==3954== Memcheck, a memory error detector
==3954== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==3954== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==3954== Command: ./program341
==3954== 
5
2  3 3   4 6
3  1 2   3 7   5 6
1  4 5
0
1  4 7
2 4
Case 1: Path =  2 1 4; 8 second delay
==3954== Invalid read of size 4
==3954==    at 0x8048F00: Vertex::~Vertex() (341.cc:48)
HERE: ==3954==    by 0x8049155: Graph::~Graph() (341.cc:103)
==3954==    by 0x8048D7C: main (341.cc:254)
==3954==  Address 0x4336198 is 0 bytes inside a block of size 8 free'd
==3954==    at 0x402AC1D: operator delete(void*) (in /usr/lib/valgrind/vgpreload_memcheck-x86-linux.so)
==3954==    by 0x804B1BA: __gnu_cxx::new_allocator<Arc*>::deallocate(Arc**, unsigned int) (new_allocator.h:100)
==3954==    by 0x804A3DA: std::_Vector_base<Arc*, std::allocator<Arc*> >::_M_deallocate(Arc**, unsigned int) (stl_vector.h:175)
==3954==    by 0x804A276: std::_Vector_base<Arc*, std::allocator<Arc*> >::~_Vector_base() (stl_vector.h:161)
==3954==    by 0x8049779: std::vector<Arc*, std::allocator<Arc*> >::~vector() (stl_vector.h:404)
==3954==    by 0x8048F3B: Vertex::~Vertex() (341.cc:45)
HERE:  ==3954==    by 0x8049135: Graph::~Graph() (341.cc:102)
==3954==    by 0x8048D7C: main (341.cc:254)
...
...