Footing (2)

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <assert.h>
#include "minqueue.h"

#define new_node() malloc(sizeof(listnode))
#define node type
#define min(a,b) ((a) < (b)) ? (a) : (b)

typedef int vertice;

typedef struct _arco {
    vertice from;
    vertice to;
    int peso;
} arco;

/* Elemento della lista di adiacenza */
typedef struct _elem {
    vertice from;
    vertice to;
    int peso;
    struct _elem *next;
} listnode;

const int INF = INT_MAX; // L'infinito di Dijkstra

// Inserisce nella lista di adiacenza del primo vertice, il secondo col peso indicato come quarto parametro
void insert(listnode**, vertice, vertice, int);

int best_cycle(int start, int n, listnode** adj);

int main(void) {
    int n, m; // n = #nodi, m = #archi
    listnode** vertici; // Liste di adiacenza
    arco* archi;
    int from, to, weight;

    FILE *fin, *fout;
    int i, j;

    fin = fopen("input.txt","r");
    fout = fopen("output.txt","w");
    assert(fin != NULL && fout != NULL);

    assert(2 == fscanf(fin, "%i %i", &n, &m)); // Leggo n & m

    vertici = calloc(n, sizeof *vertici);
    archi = malloc(2 * m * sizeof *archi);
    assert(vertici != NULL && archi != NULL);

    for(i=0;i<m;i++) {
        assert(3 == fscanf(fin, "%i %i %i", &from, &to, &weight));
        /* Zero Based */
        from--;
        to--;

        // Inserisco l'arco (inutile)
        archi[i].from = from;
        archi[i].to = to;
        archi[i].peso = weight;
        // E l'arco contrario
        archi[2*m-i-1].from = to;
        archi[2*m-i-1].to = from;
        archi[2*m-i-1].peso = weight;

        // Popolo la lista di adiacenza
        insert(vertici, from, to, weight);
        insert(vertici, to, from, weight);
    }

    int ciclo_minimo = best_cycle(0, n, vertici); // Cerco un ciclo a partire dal primo nodo
    for(i=1;i<n;i++) {

        int ciclo = best_cycle(i, n, vertici); // Cerco un ciclo per ogni altro nodo
        ciclo_minimo = (ciclo < ciclo_minimo) ? ciclo : ciclo_minimo; // Guardo se è migliore di quello che avevo prima
    }
    fprintf(fout, "%i", ciclo_minimo);

    /* CLEAN UP */
    for(i=0;i<n;i++) {
        listnode *v = vertici[i];
        while(v != NULL) {
            listnode *tmp = v;
            v = v->next;
            free(tmp);
        }
    }
    free(vertici);
    free(archi);
    fclose(fin);
    fclose(fout);
}

// Popola la lista di adiacenza di u, inserendo l'arco (u,v) di peso w
void insert(listnode** list, int u, int v, int w) {
    listnode *new = new_node();
    new->from = u;
    new->to = v;
    new->peso = w;
    new->next = NULL;

    if(list[u] == NULL) {
        list[u] = new;
    }
    else {
        listnode *curr = list[u];
        listnode *prec = NULL;
        while(curr != NULL) {
            prec = curr;
            curr = curr->next;
        }
        prec->next = new;
    }
}


int best_cycle(int start, int n, listnode** adj) {
    /* La struttura memorizzata nella coda è così formata:
     * { weight, parent, endpoint }
     * (qui chiamati rispettivamente: key, parent, nodo)
    **/
    int ciclo_minimo = INF; // L'equivalente di int best = std::numeric_limits<int>::max();
    int *distanze = malloc(n*sizeof(int)); // Equivale a  std::vector<int> dist(N, std::numeric_limits<int>::max());
    int i;

    assert(distanze != NULL);
    // Inizializzo tutto dist[] a infinito
    for(i=0;i<n;i++) {
        distanze[i] = INF;
    }

    heap_init(); // Creo la coda

    enqueue((node){0, -1, start}); // Inserisco il primo nodo (q.push({start, 0, -1}))
    while(!empty_queue()) {
        node current = extract_min(); // ( auto t = q.top(); q.pop(); )

        int u = current.nodo; // t.endpoint
        int w = current.key; // t.weight
        int p = current.parent; // t.parent

        if(distanze[u] == INF) { // Non ho mai visto il nodo
            distanze[u] = w;
        }
        else {
            // Ho già visto il nodo e quindi formo un ciclo
            ciclo_minimo = min(ciclo_minimo, distanze[u] + w);
            continue;
        }

        listnode *FS = adj[u];
        // Scorro la lista di adiacenza di u
        while(FS != NULL) {
            if(FS->to != p) { // Non torno sul padre
                enqueue((node){w + FS->peso, u, FS->to});
            }
            FS = FS->next;
        }
    }

    free(distanze);

    heap_destroy();

    return ciclo_minimo;
}