La rotta meno costosa quando la mappa cambia.

La consegna richiedeva quattro comandi: inizializzare la mappa, cambiare i costi in una regione, aggiungere o rimuovere un volo e rispondere a una domanda di viaggio. La risposta è un costo minimo, oppure −1 se il viaggio è impossibile; non occorre stampare il percorso.

Le richieste di viaggio sono molto più frequenti degli aggiornamenti e spesso interessano le stesse zone. La sfida è rispondere correttamente contenendo tempo e memoria. Un volo diretto può costare più di diversi passi terrestri: meno passi non significa meno costo.

Ho rappresentato ogni cella come un vertice di un grafo pesato. I sei vicini definiscono gli spostamenti terrestri; fino a cinque rotte aeree per cella aggiungono collegamenti direzionali. Un passo terrestre paga il costo della cella di partenza, un volo quello della rotta.

Per ogni query uso Dijkstra: mantengo il miglior costo noto per ogni cella, estraggo il candidato meno costoso e provo a migliorare i costi dei suoi vicini. Il min-heap rende efficiente la scelta del prossimo candidato. BFS ordinerebbe per numero di passi, quindi non basta quando i costi variano.

Invece di salvare sei archi terrestri per cella, ricavo i vicini dalle coordinate e dalla parità della riga. Memorizzo invece le rotte aeree, che non sono ricavabili dalla griglia. Distanze e visite usano array indicizzati con y × colonne + x.

int i_corrente = y * mappa.col + x;
char* visitato = malloc(dimMappa * sizeof(char));

for (int i = 0; i < 6; i++) {
    int ax = esagono_corrente->x + dx[i];
    int ay = esagono_corrente->y + dy[i];
    // ...
}

Rispetto a una lista esplicita degli archi terrestri, risparmio dati ridondanti: entrambe le rappresentazioni restano O(V), con V celle. Rispetto a una matrice di adiacenza V × V, evito invece spazio quadratico. Il flag di visita usa un char; restano comunque riservati cinque posti aerei per cella.

Una versione semplice di Dijkstra cercherebbe ogni volta il minimo scorrendo le celle non finalizzate. Il min-heap lo tiene alla radice: inserimento ed estrazione percorrono soltanto l’altezza dell’albero. Su questo grafo a grado limitato, il confronto teorico passa da O(V²) a O(V log V), con capacità sufficiente della coda.

while (i > 0) {
    int p = (i - 1) / 2;
    if (heap[p].costo <= heap[i].costo)
        break;
    nodo temp = heap[i];
    heap[i] = heap[p];
    heap[p] = temp;
    i = p;
}

Quando una distanza migliora, inserisco una nuova voce e salto quelle delle celle già finalizzate. Evito così di cercare e aggiornare una voce dentro l’heap. Il compromesso è lasciare duplicati: semplifica il codice, ma non garantisce meno memoria o meno operazioni rispetto a decrease-key.

if (nuovoCosto < distanza[i_univoco_dest_adiac] ||
    distanza[i_univoco_dest_adiac] == -1) {
    distanza[i_univoco_dest_adiac] = nuovoCosto;
    nodo adiacente = {ax, ay, nuovoCosto};
    heap_push(adiacente);
}

if (visitato[i_corrente]) continue;
visitato[i_corrente] = 1;

La query chiede una sola destinazione. Mi fermo quando viene estratta validamente dall’heap: con pesi non negativi la sua distanza è definitiva. Fermarsi quando viene scoperta sarebbe sbagliato, perché un percorso trovato dopo potrebbe costare meno.

if (x == x2 && y == y2) {
    printf("%d\n", corrente.costo);
    raggiunto = 1;
    free(distanza);
    free(visitato);
    return;
}

Evito le esplorazioni successive che non servono alla risposta. Il caso peggiore non cambia e gli array vengono comunque inizializzati per tutte le celle a ogni query. Questi sono benefici algoritmici; non ho misure separate di accelerazione per ciascuna scelta.

Gli estratti sono tratti da progetto.c, con omissioni indicate. Il progetto ha ottenuto 30 e lode. La pagina del codice conserva la copia disponibile e la sua nota di provenienza; la consegna ufficiale permette di verificare le regole del problema.

• Leggi tutto il codice C →
• Apri i requisiti ufficiali (PDF) →