#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <limits.h>
#include <inttypes.h>


//#define INT_MAX 100

void read_matrix (char *inputFile, int ***a, int *n, int *m, int *vf, int *nod);
int dijstra1 (int **a, int n, int vf, int nod);
void add_vector (int **v, int n, int x);
int empty_vector (int *v, int n);
int extrage_min (int **v, int n);
void print_vector(int *v, int n);
void print_Char(void *ptr);

static __inline__ unsigned long long rdtsc(void);

int* getAddressOfInter(int x);
void print_Integer(void *ptr);
void caz1(char *inputFile);
void caz2(char *inputFile);

static __inline__ unsigned long long rdtsc(void)
{
    unsigned hi, lo;
    __asm__ __volatile__ ("rdtsc" : "=a"(lo), "=d"(hi));
    return ( (unsigned long long)lo)|( ((unsigned long long)hi)<<32 );
}

int main (int argc, char **argv) {

    long long start, end;
    start = rdtsc();

    caz1("asd");
    //caz2(argv[1]);

    end = rdtsc();
    printf("\nClock : %lld \n\n",  end - start);

    return 0;
}

void caz1(char *inputFile) {
    int **a;
    int n = 0, m;
    int vf, nod;
    int i, j;
    read_matrix(inputFile, &a, &n, &m, &vf, &nod);

    for (i = 0; i < n; i++) {
        printf (" %d : ", i);
        for (j = 0; j < n; j++) {
            if (!a[i][j])
                printf(". ");
            else
                printf("%d ", a[i][j]);
        }
        printf("\n");
    }

    printf("Dist minima de la %d la %d este :%d\n", vf, nod, dijstra1(a, n, 1, 2));

    for (i = 0; i <= n; i++)
        free (a[i]);
    free (a);
}

void print_Char(void *ptr) {
    char* p = (char*) ptr;
    printf("%s ", p);
}

void print_Integer(void *ptr) {
    int* p = (int*) ptr;
    printf("%d ", *p);
}

int* getAddressOfInter(int x) {
    int *p = malloc(sizeof(int));
    *p = x;
    return p;
}


void read_matrix(char *inputFile, int ***a, int *n, int *m, int *vf, int *nod) {
    int i, j, x, y, c;

    FILE *fin = fopen ("dijstra.in", "r");
    fscanf (fin, "%d%d", m, n);

    *a = (int **) calloc (*n, sizeof (int*));
    for (int i = 0; i < *n; i++)
        (*a)[i] = (int *)calloc (*n, sizeof (int));

    for (int i = 0; i < *m; i++) {
        fscanf (fin, "%d%d%d", &x, &y, &c);
        (*a)[x - 1][y - 1] = c;
    }

    fclose(fin);
}

void add_vector(int **v, int n, int x) {

    int i = 0;
    int j = n - 1;
    while(i < n && (*v)[i] && (*v)[i] < x)
        i++;

    if ((*v)[i] == x)
        return;

    while (i < j) {
        j --;
        (*v)[j] = (*v)[j - 1];
    }

    (*v)[i] = x;
}

void print_vector(int *v, int n) {
    int i;
    for (i = 0; i < n; i++)
        printf("%d ", v[i]);
    printf("\n");
}

int empty_vector(int *v, int n) {

    int i, c = 0;
    for (i = 0; i < n; i++)
        if (v[i])
            c ++;

    return c;
}

int extrage_min (int **v, int n) {

    int i = 0, x = (*v)[0];
    while (i < n - 1) {
        if ((*v)[i+1])
            (*v)[i] = (*v)[i+1];
        else
            (*v)[i] = 0;
        i ++;
    }

    return x;
}

int dijstra1(int **a, int n, int vf, int nod) {

     int *s = calloc (n, sizeof (int));
     int *d = malloc (n * sizeof (int));
     int *p = malloc (n * sizeof (int));
     int *q = calloc (n, sizeof (int));
     int *path = calloc (n, sizeof (int));
     int i;


     s[vf] = 1;

     for (i = 0; i < n; i++) {
         if (a[vf][i]) {
             add_vector(&q, n, i);
             d[i] = a[vf][i];
             p[i] = vf;
         }
         else {
             d[i] = INT_MAX;
             p[i] = -1;
         }
     }

     while (empty_vector(q, n)) {

         int u = extrage_min(&q, n);
         s[u] = 1;

         for (i = 0; i < n; i++) {
             if (a[u][i]) {
                 if (!s[i] && d[i] > d[u] + a[u][i] && d[u] + a[u][i] > 0) {
                     d[i] = d[u] + a[u][i];
                     p[i] = u;
                     add_vector(&q, n, i);
                 }
             }
         }
     }

     int index = 0;
     i = nod;
     while (i != -1) {
         path[index] = i;
         index ++;
         i = p[i];
     }
     printf ("Drum : ");
     print_vector(path, n);
     i = d[nod];

     FILE *fout = fopen ("dijstra.out", "w");
     for (i = 1; i < n; i++){
         fprintf(fout, "%d ", d[i]);
     }
     fclose (fout);

     free (s);
     free (p);
     free (d);
     free (q);
     free (path);

     return i;
}