# Execution killed Railroad

**URL:** <https://forum.olinfo.it/t/execution-killed-railroad/7936>\
**Category:** Aiuto\
**Created:** [27 Dicembre 2022, 8:33pm UTC](https://forum.olinfo.it/t/execution-killed-railroad/7936 "2022-12-27T20:33:31Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![andrexlenx](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/35a633/32.png) [@andrexlenx](https://forum.olinfo.it/u/andrexlenx)\
**Post date:** [27 Dicembre 2022, 8:33pm UTC](https://forum.olinfo.it/t/execution-killed-railroad/7936/1 "2022-12-27T20:33:31Z")

</div>

Salve a tutti  
Ho implementato la prima parte del problema in questo modo:

```auto
#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).

Grazie in anticipo

---

<div class="post-metadata">

**Author:** ![cip999](https://forum.olinfo.it/user_avatar/forum.olinfo.it/cip999/32/58_2.png) [@cip999](https://forum.olinfo.it/u/cip999)\
**Post date:** [28 Dicembre 2022, 11:26am UTC](https://forum.olinfo.it/t/execution-killed-railroad/7936/2 "2022-12-28T11:26:40Z")

</div>

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:

```auto
==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?).

---

<div class="post-metadata">

**Author:** ![bortoz](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/b/7c8e57/32.png) [@bortoz](https://forum.olinfo.it/u/bortoz)\
**Post date:** [28 Dicembre 2022, 11:36am UTC](https://forum.olinfo.it/t/execution-killed-railroad/7936/3 "2022-12-28T11:36:12Z")

</div>

> [@cip999](#):
>
> Devi leggere l’input da standard input (`cin`), non da file.

Questo non è vero, si può leggere sia da file che da standard input.

Il vero problema è che hai scritto `fstream` invece di `ifstream`.

---

<div class="post-metadata">

**Author:** ![cip999](https://forum.olinfo.it/user_avatar/forum.olinfo.it/cip999/32/58_2.png) [@cip999](https://forum.olinfo.it/u/cip999)\
**Post date:** [28 Dicembre 2022, 12:06pm UTC](https://forum.olinfo.it/t/execution-killed-railroad/7936/4 "2022-12-28T12:06:56Z")

</div>

Ops, sorry. Tutto il resto però è vero (spero). 😄