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

// a fibonacci node within a circular, doubly-linked list
typedef struct fibnode
{
  void *key;                // pointer to key, application data
  int degree;               // size of children list
  char mark;                // set if a children was previously removed
  struct fibnode *left;
  struct fibnode *right;
  struct fibnode *parent;   // parent of this node, NULL if it is root
  struct fibnode *children; // children of this node, NULL if it has no children
} FibNode;

// min fibonacci heap
typedef struct fibheap
{
  FibNode *min;             // minimum in this heap, NULL if heap is empty
  int size;                 // number of nodes in this heap
} FibHeap;

// creates and returns a new, empty fibonacci heap
extern FibHeap *fibNewHeap();
// creates a node with the given key and inserts it in the heap
// returns a handle to the newly created node
// applications should free the memory of the returned nodes
extern FibNode *fibInsertKey(FibHeap *h, void *key);
// inserts an already created node
extern void fibInsertNode(FibHeap *h, FibNode *node);
// extracts a node off the heap, frees the node's memory
// returns a pointer to the node's key
extern void *fibExtractKey(FibHeap *h);
// same as above, does not free memory
// returned node can be inserted in another heap
extern FibNode *fibExtractNode(FibHeap *h);
// promotes node from a given heap
extern void fibPromoteNode(FibHeap *h, FibNode *n);
// frees a heap's memory, i.e. nodes in the heap; this does not affect the keys
extern void fibFreeMem(FibHeap *h);


// external function used to order the keys of nodes
// should return <0, 0, >0 iff x < y, x == y, x > y
extern int fibCompareKey(void *x, void *y);

static const int INFINITY = 0x7FFFFFFF;

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

  // do dijkstra
  GraphNode *min, *adjNode;
  while(pq->min)
  {
    min = (GraphNode*)fibExtractKey(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;
        fibPromoteNode(pq, fibNodes[list->index]);
      }
    }
  }

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

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

// helper procedure, computes int log two of a number
static inline int logtwo(int x){ int log = 0; while(x >>= 1) log++; return log;}
// helper procedure for creating a single element circular dlinked list
static inline FibNode* dlistNew();
// helper procedure for inserting a list (or a node) in a dlinked list just
// before a dest node
static inline void dlistInsert(FibNode *dest, FibNode *list);
// helper procedure for removing a node from its circular dlinked list
// node is preserved, has no effect on a list with one item
static inline void dlistRemove(FibNode *n);


// helper procedure for creating a single element circular dlinked list
static inline FibNode* dlistNew();
// helper procedure for consolidating a fibonacci heap
// links trees in the root list so that there's at most one tree root with a 
// particular degree
void fibConsolidate(FibHeap *h);
// helper procedure for linking two trees from a fibonacci heap
static inline void fibLink(FibNode *dest, FibNode *src);
// helper procedure for cutting a node from a fibonacci heap
static inline void fibCutNode(FibHeap *h, FibNode *n);
// helper procedure for freeing a tree of nodes
void fibFreeNodes(FibNode *n);


FibHeap *fibNewHeap()
{
  FibHeap *heap = calloc(1, sizeof(FibHeap));
  if(!heap)
  {
    fprintf(stderr, "fibNewHeap: Could not allocate memory for" 
      "Fibonacci heap\n");
    exit(EXIT_FAILURE);
  }
  return heap;
}

// inserts a node with the given key in an existing heap
// returns a handle to the node
FibNode *fibInsertKey(FibHeap *h, void *key)
{
  FibNode *n = dlistNew();
  // set key, degree is 0, mark is false, parent is null
  n->key = key;
  fibInsertNode(h, n);
  return n;
}

void fibInsertNode(FibHeap *h, FibNode *n)
{
  // if the heap is empty, create first node in root list
  // otherwise, add it to the root list, just before the minimum node
  if(!h->min) h->min = n;
  else dlistInsert(h->min, n);
  h->size++;
  if(fibCompareKey(n->key, h->min->key) < 0) h->min = n;
}

void *fibExtractKey(FibHeap *h)
{
  FibNode *n = fibExtractNode(h);
  void *result = n->key;
  free(n);
  return result;
}

// extracts the minimum node's key off the heap
FibNode *fibExtractNode(FibHeap *h)
{
  if(!h->min) return NULL;
  FibNode *min = h->min;
  // place extracted node's children in the root list
  FibNode *child = min->children;
  if(child)
  {
    FibNode *end = child;
    do
    {
      child->parent = NULL;
      child = child->right;
    } while (child != end);
    dlistInsert(min, child);
  }
  dlistRemove(min);
  // if heap is now empty, there's no minimum
  // otherwise assign some temporary minimum and consolidate heap
  if(min->right == min) h->min = NULL;
  else
  {
    h->min = min->right;
    fibConsolidate(h);
  }

  h->size--;
  min->degree = min->mark = 0;
  min->children = min->parent = NULL;
  min->left = min->right = min;
  return min;
}

// helper procedure for consolidating a fibonacci heap
// links trees in the root list so that there's at most one tree root with a
// particular degree
void fibConsolidate(FibHeap *h)
{
  static const float LOG_BASE_CHANGE = 1.4413f;
  // degrees[i] is a pointer to a root node with degree i
  // the maximum degree of a node in a heap of size n is bounded by
  // log_base_golden_ratio_n, which is ~ 1.4413 * log_base_two_n
  int maxDegree = (float)(logtwo(h->size) + 1) * LOG_BASE_CHANGE;
  FibNode *degrees[maxDegree + 1];
  for(int i = 0; i <= maxDegree; ++i) degrees[i] = NULL;
  FibNode *iter = h->min, *end = iter;
  FibNode *root, *other;

  // iterate through the list of tree roots
  do
  {
    root = iter;
    // while there are tree roots with the same degree, make the greater tree
    // the child of the smaller one
    while((other = degrees[root->degree]))
    {
      if(fibCompareKey(other->key, root->key) < 0)
      {
        FibNode *aux = root;
        root = other;
        other = aux;
      }
      degrees[root->degree] = NULL;
      // make other the child of root, careful if other was end of root list
      // or if other is current root in iteration
      if(other == iter) iter = iter->left;
      if(other == end) end = end->right;
      fibLink(root, other);
    }
    // this is where intermediate consolidated trees are placed, i.e. ones that
    // are still in the root list, so check for new minimum
    degrees[root->degree] = root;
    if(fibCompareKey(root->key, h->min->key) <= 0) h->min = root;
    // move to the next root in list
  } while((iter = iter->right) != end);
}

void fibPromoteNode(FibHeap *h, FibNode *n)
{
  // if node is not root and new key is less than its parent
  // cut the node from its tree
  if(n->parent && fibCompareKey(n->key, n->parent->key) < 0)
  {
    FibNode *cutNode = n, *cutParent;
    do
    {
      // keep a pointer to this node's parent if it is marked
      // because fibCutNode will mark parent anyway
      cutParent = cutNode->parent->mark ? cutNode->parent : NULL;
      fibCutNode(h, cutNode);
      // cascade the cut while parent node was already marked and not root
    } while((cutNode = cutParent) && cutNode->parent);
  }
  // update the minimum if required
  // do this only now, so fibCutNode will have a valid root list of 'h'
  if(fibCompareKey(n->key, h->min->key) < 0) h->min = n;
}

void fibFreeMem(FibHeap *h)
{
  if(h->min) fibFreeNodes(h->min);
  free(h);
}

void fibFreeNodes(FibNode *iter)
{
  FibNode *next, *end = iter;
  do
  {
    if(iter->children) fibFreeNodes(iter->children);
    next = iter->right;
    free(iter);
  }
  while((iter = next) != end);
}


static inline void fibLink(FibNode *dest, FibNode *src)
{
  // remove tree root from root list, dest is now its parent
  dlistRemove(src);
  // isolate removed root
  src->left = src->right = src;
  src->parent = dest;
  // special case, destination has no children, src will be the only child
  if(!dest->children) dest->children = src;
  else dlistInsert(dest->children, src);
  dest->degree++;
  src->mark = 0;
}

static inline void fibCutNode(FibHeap *h, FibNode *n)
{
  FibNode *parent = n->parent;
  // remove node from parent's children list
  dlistRemove(n);
  // update parent's children pointer accordingly
  if(parent->children == n) parent->children = n->right == n ? NULL : n->right;
  // mark parent, it has just lost a child
  parent->mark = 1;
  parent->degree--;

  // isolate node and add to root list
  n->left = n->right = n;
  n->mark = 0;
  n->parent = NULL;
  dlistInsert(h->min, n);
}


// helper procedure for creating a single element circular dlinked list
static inline FibNode* dlistNew()
{
  FibNode *node = calloc(1, sizeof(FibNode));
  if(!node)
  {
    fprintf(stderr, "dlistNew: Could not allocate memory for Fibonacci node"
      " list\n");
    exit(EXIT_FAILURE);
  }

  node->left = node;
  node->right = node;
  return node;
}

// helper procedure for inserting a list (or a node) in a dlinked list just
// before a dest node
static inline void dlistInsert(FibNode *dest, FibNode *list)
{
  FibNode *destEnd = dest->left;
  FibNode *listEnd = list->left;

  destEnd->right = list;
  list->left = destEnd;
  listEnd->right = dest;
  dest->left = listEnd;
}

// helper procedure for removing a node from its circular dlinked list
// node is preserved, has no effect on a list with one item
static inline void dlistRemove(FibNode *n)
{
  n->left->right = n->right;
  n->right->left = n->left;
}