The lowest-cost route on a changing map.

The assignment required four commands: initialize the map, change costs in a region, add or remove an air route, and answer a travel query. The answer is a minimum cost, or −1 if no journey is possible; the route itself does not need to be printed.

Travel queries are much more frequent than updates and often concern the same areas. The challenge is to answer correctly while controlling time and memory. A direct flight can cost more than several land moves: fewer steps do not mean a lower cost.

I represented each cell as a vertex in a weighted graph. Its six neighbours define land moves; up to five outgoing air routes add directed connections. A land move pays the departure cell’s cost, while a flight pays the route’s cost.

For each query I use Dijkstra: maintain the best known cost for each cell, extract the cheapest candidate, and try to improve its neighbours’ costs. A min-heap makes candidate selection efficient. BFS orders by number of steps, which is insufficient when costs vary.

Instead of storing six land edges per cell, I derive neighbours from coordinates and row parity. I store air routes explicitly because the grid cannot determine them. Distances and visited flags use arrays indexed by y × columns + 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];
    // ...
}

Compared with explicit land-edge lists, this saves redundant data: both representations remain O(V), for V cells. Compared with a V × V adjacency matrix, it avoids quadratic space. Each visited flag uses a char; five air-route slots are still reserved per cell.

A simple version of Dijkstra would scan unfinished cells to find every next minimum. The min-heap keeps it at the root: insertion and extraction traverse only the tree’s height. On this bounded-degree graph, the theoretical comparison is O(V²) versus O(V log V), with sufficient queue capacity.

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

When a distance improves, I insert a new entry and skip entries for finalized cells. This avoids locating and updating an entry inside the heap. The trade-off is duplicate entries: it simplifies the code but does not guarantee less memory or fewer operations than 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;

A query asks for one destination. I stop when it is validly extracted from the heap: with non-negative weights its distance is final. Stopping at discovery would be wrong, since a later path could be cheaper.

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

This avoids later exploration that the answer does not need. The worst case is unchanged, and arrays are still initialized for every cell on each query. These are algorithmic benefits; I do not have separate speed-up measurements for each choice.

The excerpts come from progetto.c, with omissions marked. The project received 30/30 with honours. The code page preserves the available copy and its provenance note; the official assignment documents the problem’s rules.

• Read the full C source →
• Open the official requirements (PDF) →