график — ошибка времени выполнения UVa Online Judge C ++ (341 — безостановочный ход)

Я пытался сделать 341 Непрерывная проблема путешествия на UVA Judge Online, но когда я отправляю свой код, судья говорит, что есть ошибка времени выполнения (RE), и я не могу ее обнаружить. Я решил проблему с помощью алгоритма Дейкстры и графа списка смежности. Когда я проверил пример ввода, моя программа работает нормально, но я не знаю, что делать, чтобы пропустить эту ошибку времени выполнения! Мой код ниже

#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;
}

——————————-РЕДАКТИРОВАТЬ——————————
Я сделал вещи в коде, чтобы избежать ошибки времени выполнения. Сначала я исправил свои ошибки утечки памяти (спасибо us2012 и NPE!), Затем я лечил случаи отключенных графиков. Это версия кодекса, которая была принята судьей.

1

Решение

Проблема здесь:

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

Деструктор вызывается автоматически, когда вы delete это, по сути, вы называете это дважды. Вот как вы узнаете об этом, когда вы этого не знаете: (соответствующие строки отмечены как "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)
...
...
0

Другие решения

Других решений пока нет …

По вопросам рекламы ammmcru@yandex.ru
Adblock
detector