Dijkstra (Execution Killed with signal 11)

Aiuto
1

Il correttore continua a darmi Execution killed with signal 11 (could be triggered by violating memory limits) su ogni task. Non riesco a capire dove sia l’errore…

#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
#include<limits>
using namespace std;


const long long int infinito = numeric_limits<long long int>::max();

typedef pair<long long int,long long int> ii;
typedef vector<ii>vii;
typedef vector<vii> mii;

struct step 
{
	long long int corrente;
	long long int distanza;
	step(){}
	step(long long int c,long long int d)
	:corrente(c),distanza(d){}
	bool operator<(const step&s)
	const{return distanza>s.distanza;}
};
long long int vertici,archi;
long long int sorgente,destinazione;
mii adj;
long long int dijkstra(mii &adj,long long int sorgente,long long int destinazione)
{
	vector<long long int> distance(adj.size(),infinito);
	priority_queue<step> pq;
	pq.push({sorgente,0});
	while(!pq.empty())
	{
		step head = pq.top();
		pq.pop();
		if(distance[head.corrente] == infinito)
		{
			distance[head.corrente] = head.distanza;
		
			if(head.corrente == destinazione) return head.distanza;
			for(auto x : adj[head.corrente])
				if(distance[x.first]>head.distanza+x.second)
					pq.push({x.first,head.distanza+x.second});		
		}
	}
	return distance[destinazione];
}

int main(int argc, char** argv) {
	ifstream in("input.txt");
	ofstream out("output.txt");
	in>>vertici>>archi>>sorgente>>destinazione;
	for(long long int x = 0,i,j,peso;x<archi;x++)
	{
		in>>i>>j>>peso;
		adj[i].push_back({j,peso});
	}
	out<<dijkstra(adj,sorgente,destinazione);
	return 0;
}
2

Credo che l’errore sia in questo loop:

for(long long int x = 0,i,j,peso;x<archi;x++)
{
    in>>i>>j>>peso;
    adj[i].push_back({j,peso});
}

adj è un vector<vector<ii> >, ma non inizializzi gli elementi del vector “di fuori”. Intendo che il vector di vector ha dimensione 0 all’inizio dell’esecuzione, e quindi accedere all’elemento i va fuori dalle sue dimensioni. Dovresti inizializzare adj all’inizio dell’esecuzione con qualcosa del tipo di
adj.assign(vertici, vector<ii>());
Inoltre i e j vanno da 1 a N, mentre gli indici dell’array vanno da 0 a N - 1, quindi o sottrai uno a tutti gli indici in input oppure ingrandisci di uno le dimensioni di adj.
Un’altra cosa che ho notato è che la priority_queue è al contrario, se nei parametri del template metti solo il tipo di dati ti ritorna gli elementi a partire dal più grande. Dichiarala come
priority_queue<step, vector<step>, greater<step> >.
step è il tipo di elementi, vector<step> è il contenitore utilizzato dalla coda e greater<step> è il comparatore che te la ordina in ordine crescente.

Dario

1 Mi Piace
3

Il compilatore mi da tanti errori se scrivo questo. Se lo lascio com’era, il problema della memoria si risolve e mi da tutti outputs non corretti tranne uno

4

In alternativa puoi “negare” i valori degli archi (moltiplicandoli per -1) così che il valore più grande coincida con il più piccolo moltiplicato per -1.

Comunque per utilizzare greater con una struct devi definire l’operatore >, altrimenti puoi anche definire tu una funzione per confrontare le struct e usarla al posto di greater.

1 Mi Piace
5

Quando nel main stai riempiendo il vector adj stai cercando di accedere a memoria non allocata scrivendo adj[I]. Allocated la memoria aggiungendo prima di quel loop adj.resize(vertici+1).
Il +1 perché mi sembra di ricordare che nel problema Dijkstra il primo nodo é il numero 1 e non il numero 0. Poi invece di tutti quei typedef era molto più semplice e chiaro dichiarare adj cosí:
vector<vector<pair<int,int>>> adj;
Spero di essere stato chiaro, ciao.