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