Problema Collo di bottiglia

Sto provando questo problema, e la mia idea è quella di eseguire prima di tutto una bfs per avere la distanza minima in nodi tra i due computer (William e Luca), e poi dijkstra per avere la portata minima.
Ovviamente in dijkstra invece di avere la somma dei pesi degli archi come lunghezza di un percorso uso il minimo dei pesi.
Per ora ho implementato solo la prima parte, la visita in ampiezza, che in locale funziona senza problemi. Per prova l’ho caricata sul correttore (sottoposizione 48228), dove ovviamente ho avuto 0/100. La cosa strana, però, è che alcuni testcase me li dà come falliti con questo errore: “Execution killed with signal 11 (could be triggered by violating memory limits)”. Questo è il codice che uso, è possibile che esaurisca veramente la memoria?

#include <vector>
#include <utility>
#include <list>
#include <bitset>
using namespace std;

vector<vector<pair<int, int> > > *arcs;

// bfs
int calculateMinLength(int startNode, int finalNode)
{
    //       node  length
    list<pair<int, int> > queue;
    bitset<MAXN> visited;
    queue.push_back(make_pair(startNode, 0));
    visited[startNode] = true;
    
    vector<pair<int, int> >::iterator it;
    
    while(!queue.empty())
    {
        // get next node
        pair<int, int> node = queue.front();
        queue.pop_front();
        
        // check if we reached our goal
        if(node.first == finalNode)
            return node.second;
        
        // otherwise continue the visit
        vector<pair<int, int> > arcList = (*arcs)[node.first];
        for(it = arcList.begin(); it != arcList.end(); ++it)
        {
            if(!visited[(*it).first])
            {
                visited[(*it).first] = true;
                queue.push_back(make_pair((*it).first, node.second + 1));
            }
        }
    }
    
    return -1;
}

// modified Dijkstra
int calculateMinCapacity(int start, int end, int maxLen)
{
    return 12;
}

int Analizza(int N, int M, int W, int L, int arc_from[], int arc_to[], int cap[], int, int)
{
    // save all arcs in a better format
    arcs = new vector<vector<pair<int, int> > >(M);
    for(int i = 0; i < M; i++)
    {
        (*arcs)[arc_from[i]].push_back(make_pair(arc_to[i], cap[i]));
        (*arcs)[arc_to[i]].push_back(make_pair(arc_from[i], cap[i]));
    }
    
    // calculate maximum possible length with a bfs
    int maxLen = calculateMinLength(W, L);
    
    // now execute the modified dijkstra search with the maximum length
    int capacity = calculateMinCapacity(W, L, maxLen);
    
    printf("%d\n", capacity);
    
    return 0;
}

Dario

L’errore Execution killed with signal 11 (could be triggered by violating memory limits) non è sempre legato all’esaurimento della memoria. Può accadere:

  1. Quando il programma tenta di accedere a memoria non allocata, per esempio:
    int a[10]; for (int i=0; i<1000; i++) a[i] = i*i;
  2. Quando il programma tenta di allocare troppa memoria.
  3. Quando il programma “si perde” in una ricorsione infinita (o troppo profonda). È una conseguenza del punto 2.

Nel tuo caso sospetto che sia il caso 1.

Ok grazie mille,
dopo la gara pre oii riproverò a farlo.

1 Mi Piace