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

typedef struct llist
{
  int index;
  int length;
  struct llist *next;
} LList;

typedef struct graphnode
{
  int dist;             // distance from source
  int hindex;           // position in the heap
  LList *outList;  // adjacency list
} GraphNode;

typedef struct g
{
  GraphNode *nodes;     // array of nodes
  int size;             // number of nodes in the g
} Graph;

Graph *graphNew(int size)
{
  Graph *g;
  if((g = (Graph*) calloc(1, sizeof(Graph))) == NULL)
  {
    fprintf(stderr, "Cannot allocate memory for g.\n");
    return NULL;
  }
  if((g->nodes = (GraphNode*) calloc(size, sizeof(GraphNode))) == NULL)
  {
    fprintf(stderr, "Cannot allocate memory for nodes array.\n");
    free(g);
    return NULL;
  }
  g->size = size;

  return g;
}

Graph *graphRead (char *filename)
{
  FILE *fp;
  // check for file, file format and g mem allocation
  if ((fp = fopen(filename, "r")) == NULL) {
    fprintf(stderr,"cannot open file %s\n", filename);
    return NULL;
  }
  int numNodes, numEdges;
  Graph *g;
  LList *adjNode;
  char buf[100];

  fscanf(fp, "%d %d%*[^1-9]", &numNodes, &numEdges);
  g = graphNew(numNodes + 1);
  for(int count = 1, src; count <= numEdges; ++count)
  {
    adjNode = (LList*)malloc(sizeof(LList));
    fgets(buf, 100, fp);
    sscanf(buf, "%d %d %d\n", &src, &(adjNode->index), &(adjNode->length));
    adjNode->next = g->nodes[src].outList;
    g->nodes[src].outList = adjNode;
  }
  fclose(fp);
  return g;
}

// min binary heap
struct binheap
{
  int capacity; // size of the array
  int size;     // number of elements currently in the heap
  void *el[];   // array of pointer to elements
};
typedef struct binheap BinHeap;

// creates and returns a new, empty heap with the given capacity
BinHeap *binNewHeap(int capacity);
// inserts the given key into the heap
void binInsertKey(BinHeap *h, void *key);
// extracts and returns element at the top of the heap, or NULL if it's empty
void *binExtractKey(BinHeap *h);
// the following two procedures call binSetKeyPos() on each update of a key's
// position
// decreases/sifts a key
void binUpNode(BinHeap *h, int nindex);
// increases/percolates a key
void binDownNode(BinHeap *h, int nindex);
// frees the memory allocated for the given heap, doesn't affect the keys
void binFreeMem(BinHeap *h);

// following two procedures should pe provided by the application
// establishes keys' order, should return <0, 0, >0 iff x < y, x == y, x > y
extern int binCompareKey(void *x, void *y);
// sets the position of a key in its heap
extern void binSetKeyPos(void *key, int index);

static const int INFINITY = 0x7FFFFFFF;

int main(void)
{
  Graph *g = graphRead("dijkstra.in");
  // init priority queue, save nodes' handles
  BinHeap *pq = binNewHeap(g->size);
  g->nodes[1].dist = 0;
  binInsertKey(pq, g->nodes + 1);
  for(int i = 2; i < g->size; ++i)
  {
    g->nodes[i].dist = i;
    binInsertKey(pq, g->nodes + i);
  }

  GraphNode *min, *adjNode;
  while((min = (GraphNode*)binExtractKey(pq)))
  {
    if(min->dist == INFINITY) break;
    for(LList *list = min->outList; list; list = list->next)
    {
      adjNode = g->nodes + list->index;
      if(adjNode->dist > min->dist + list->length)
      {
        adjNode->dist = min->dist + list->length;
        binUpNode(pq, adjNode->hindex);
      }
    }
  }

  // output results
  FILE *out = fopen("dijkstra.out", "w");
  for(int i = 2; i < g->size; ++i)
    if(g->nodes[i].dist == INFINITY) fprintf(out, "0 ");
    else fprintf(out, "%d ", g->nodes[i].dist);
  fprintf(out, "\n"); fclose(out);
  return 0;
}


BinHeap *binNewHeap(int capacity)
{
  BinHeap *h = (BinHeap*)malloc(sizeof(BinHeap) + (capacity + 1)*sizeof(void*));
  if(!h)
  {
    fprintf(stderr, "binNewHeap: Could not allocate memory for" 
      " binary heap\n");
    exit(EXIT_FAILURE);
  }
  h->size = 0;
  h->capacity = capacity;

  return h;
}

void binInsertKey(BinHeap *h, void *key)
{
  if(h->size == h->capacity)
  {
    fprintf(stderr, "binInsertKey: Cannot insert node, heap is full\n");
    exit(EXIT_FAILURE);
  }
  h->el[++h->size] = key;
  binUpNode(h, h->size);
}

void *binExtractKey(BinHeap *h)
{
  if(h->size == 0) return NULL;
  void *result = h->el[1];

  h->el[1] = h->el[h->size--];
  binDownNode(h, 1);

  return result;
}

void binUpNode(BinHeap *h, int nindex)
{
  // save node which is being promoted
  void *node = h->el[nindex];
  int parent = nindex / 2;

  // move up as much as possible, dragging parent nodes
  while(nindex > 1 && binCompareKey(node, h->el[parent]) < 0)
  {
    h->el[nindex] = h->el[parent];
    binSetKeyPos(h->el[parent], nindex);
    nindex = parent; parent /= 2;
  }
  // place promoted node in final position
  h->el[nindex] = node;
  binSetKeyPos(node, nindex);
}

void binDownNode(BinHeap *h, int nindex)
{
  void *node = h->el[nindex];
  // index of the last node that has children
  int lastParent = h->size / 2;
  int least, other;

  // while node has children
  while(nindex <= lastParent)
  {
    // find least child, assume it is left child
    least = nindex * 2;
    other = least + 1;
    if(other <= h->size && binCompareKey(h->el[other], h->el[least]) < 0)
      least = other;
    // stop if node is less than both children
    if(binCompareKey(node, h->el[least]) < 0) break;
    // otherwise swap least child with node
    h->el[nindex] = h->el[least];
    binSetKeyPos(h->el[least], nindex);
    nindex = least;
  }
  // place node in final position
  h->el[nindex] = node;
  binSetKeyPos(node, nindex);
}

void binFreeMem(BinHeap *h)
{
  free(h->el);
  free(h);
}

inline int binCompareKey(void *x, void *y)
{
  return ((GraphNode*)x)->dist - ((GraphNode*)y)->dist;
}

inline void binSetKeyPos(void *key, int index)
{
  ((GraphNode*)key)->hindex = index;
}