Salve a tutti
Ho implementato la prima parte del problema in questo modo:
#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <fstream>
using namespace std;
struct Nodo{
vector<int> abj;
vector<int> costi;
};
pair<int, vector<int>> dijkstra(vector<Nodo> &g) {
int to;
int weight;
int N = g.size();
vector<int> dist(N,numeric_limits<int>::max());
vector<int> pat(N,numeric_limits<int>::max());
dist[0] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
pq.emplace(0, 0);
pair<int, int> curr;
int v, weight_to_v;
while (!pq.empty()) {
curr = pq.top();
weight_to_v = curr.first;
v = curr.second;
pq.pop();
if (v==N-1)
break;
if (weight_to_v != dist[v])
continue;
for (int i = 0; i < g[v].abj.size(); i++) {
to = g[v].abj[i];
weight = g[v].costi[i];
if (dist[v] + weight < dist[to]) {
dist[to] = dist[v] + weight;
pat[to] = v;
pq.emplace(dist[to], to);
}
}
}
return {dist[N-1],pat};
}
int main() {
fstream in("input.txt");
ofstream out("output.txt");
int N;
int M;
in>>N>>M;
int a,b,c;
vector<Nodo> grafo(N);
for (int i = 0; i < M; ++i) {
in>>a>>b>>c;
grafo[a].abj.push_back(b);
grafo[a].costi.push_back(c);
grafo[b].abj.push_back(a);
grafo[b].costi.push_back(c);
}
pair<int,vector<int>> ez;
ez = dijkstra(grafo);
cout<<ez.first<<endl;
/*
*/
return 0;
}
sto avendo un problema con la funzione dijkstra, dopo varie sottoposizioni ho individuato l’istruzione che manda in crash il programma, ovvero dist[0] = 0 perchè sembrerebbe che il vettore dist non venga allocato ma non riesco a capire il motivo.
Se provo a commentare la chiamata alla funzione, l’errore non avviene nell’acquisizione dei dati in input (dando semplicemente output non corretto), ciò significa che il vettore di nodi viene correttamente inizializato ad N, (altrimenti anch’esso andrebbe in errore con un qualsiasi valore di a).
Devi leggere l’input da standard input (cin), non da file.
Altrimenti stai leggendo da un file inesistente, e la variabile N non viene inizializzata. Questo risulta in un undefined behavior: il valore di N al momento in cui il vector grafo viene allocato è imprevedibile e dipende da tanti fattori, tra cui il compilatore usato e la CPU su cui viene eseguito il programma. Il valore di N può anche essere diverso in diverse esecuzioni dello stesso eseguibile!
Nel nostro caso, in realtà , quello che succede è abbastanza prevedibile: il valore di N è 0 al momento della dichiarazione, e rimane 0 (puoi accorgertene con un assert). Quindi grafo non viene allocato. Dato che, nella funzione dijkstra, la variabile locale N viene inizializzata alla dimensione di g, anch’essa vale 0, e quindi dist e pat sono vector vuoti (come avevi ipotizzato).
Tanto per chiarire che il fatto che N (nel main) valga 0 è un caso eccezionale e non la norma, se compilo il tuo sorgente in locale con g++ e la flag -fsanitize=address (ed eseguo in una directory in cui non esiste input.txt), ottengo il seguente errore:
==423008==ERROR: AddressSanitizer: allocator is out of memory trying to allocate 0x55bac31a0 bytes
#0 0x7f348c4bd1c7 in operator new(unsigned long) ../../../../src/libsanitizer/asan/asan_new_delete.cpp:99
#1 0x55cba1079902 in __gnu_cxx::new_allocator<Nodo>::allocate(unsigned long, void const*) /usr/include/c++/11/ext/new_allocator.h:127
#2 0x55cba1079902 in std::allocator_traits<std::allocator<Nodo> >::allocate(std::allocator<Nodo>&, unsigned long) /usr/include/c++/11/bits/alloc_traits.h:464
#3 0x55cba1079902 in std::_Vector_base<Nodo, std::allocator<Nodo> >::_M_allocate(unsigned long) /usr/include/c++/11/bits/stl_vector.h:346
#4 0x55cba1079902 in std::_Vector_base<Nodo, std::allocator<Nodo> >::_M_create_storage(unsigned long) /usr/include/c++/11/bits/stl_vector.h:361
#5 0x55cba1079902 in std::_Vector_base<Nodo, std::allocator<Nodo> >::_Vector_base(unsigned long, std::allocator<Nodo> const&) /usr/include/c++/11/bits/stl_vector.h:305
#6 0x55cba1079902 in std::vector<Nodo, std::allocator<Nodo> >::vector(unsigned long, std::allocator<Nodo> const&) /usr/include/c++/11/bits/stl_vector.h:511
#7 0x55cba1079902 in main /tmp/test/test.cpp:56
ovvero il programma cerca di allocare un vector di Nodo che eccede la memoria disponibile. Questo è dovuto al fatto che il valore di N non è 0, ma un intero positivo grande o un intero negativo (domanda: cosa succede in quest’ultimo caso?).
