#define _CRT_SECURE_NO_WARNINGS

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

typedef struct weightedListNode {
	int node;
	int weight;
	weightedListNode* next;
} weightedListNode;

typedef struct {
	int node_count;
	int edge_count;
	weightedListNode** adjacencyList;
} weightedGraph;

typedef struct {
	int distance;
	int node;
} heapNode;

typedef struct {
	heapNode* heap;
	int size;
} Priority_Queue;


Priority_Queue* queue;
int* distance;
bool* visited;


weightedListNode* add_edge(weightedGraph*, int, int, int);
void read_weightedGraph(weightedGraph*, const char*);

Priority_Queue* create_PriorityQueue(int);
inline int get_parent_index(int);
inline int get_leftChild_index(int);
inline int get_rightChild_index(int);
inline bool is_leaf(int, int);
inline void swap(heapNode*, heapNode*);

void heapifyDOWN(Priority_Queue*, int);
void heapifyUP(Priority_Queue*, int);

heapNode extract_min(Priority_Queue*);
void insert(Priority_Queue*, heapNode);

void dijkstra(weightedGraph*);

void print_array(const char*, int*, int, int);


void main(int argc, char* argv[]) {
	weightedGraph* graph = (weightedGraph*)malloc(sizeof(weightedGraph));
	read_weightedGraph(graph, "dijkstra.in");
	dijkstra(graph);
	print_array("dijkstra.out", distance, 2, graph->node_count);
}


weightedListNode* add_edge(weightedGraph* graph, int node1, int node2, int weight) {
	weightedListNode* newNode = (weightedListNode*)malloc(sizeof(weightedListNode));
	newNode->node = node2;
	newNode->weight = weight;
	newNode->next = graph->adjacencyList[node1];
	graph->adjacencyList[node1] = newNode;

	return newNode;
}

void read_weightedGraph(weightedGraph* graph, const char* fileName) {
	FILE* input = fopen(fileName, "r");
	if (input == NULL) exit(1);

	fscanf(input, "%d %d",
		&graph->node_count,
		&graph->edge_count);
	graph->adjacencyList = (weightedListNode**)calloc(graph->node_count + 1, sizeof(weightedListNode*));
	for (int i = 0, node1, node2, weight; i < graph->edge_count; i++) {
		fscanf(input, "%d %d %d", &node1, &node2, &weight);
		add_edge(graph, node1, node2, weight);
	}

	fclose(input);
}

Priority_Queue* create_PriorityQueue(int capacity) {
	Priority_Queue* queue = (Priority_Queue*)malloc(sizeof(Priority_Queue));
	queue->heap = (heapNode*)malloc(capacity * sizeof(heapNode));
	queue->size = 0;

	return queue;
}

inline int get_parent_index(int index) { return (index - 1) / 2; }

inline int get_leftChild_index(int index) { return 2 * index + 1; }

inline int get_rightChild_index(int index) { return 2 * index + 2; }

inline bool is_leaf(int index, int heap_size) {
	int leftChildIndex = get_leftChild_index(index);
	return leftChildIndex >= heap_size;
}

inline void swap(heapNode* a, heapNode* b) {
	heapNode aux = *a;
	*a = *b;
	*b = aux;
}

void heapifyDOWN(Priority_Queue* queue, int index) {
	if (is_leaf(index, queue->size) == true) return;

	int leftChildIndex = get_leftChild_index(index);
	int rightChildIndex = get_rightChild_index(index);
	int smallestChildIndex = index;

	if (leftChildIndex < queue->size &&
		queue->heap[smallestChildIndex].distance > queue->heap[leftChildIndex].distance)
		smallestChildIndex = leftChildIndex;
	if (rightChildIndex < queue->size &&
		queue->heap[smallestChildIndex].distance > queue->heap[rightChildIndex].distance)
		smallestChildIndex = rightChildIndex;

	if (index != smallestChildIndex) {
		swap(&queue->heap[index], &queue->heap[smallestChildIndex]);
		heapifyDOWN(queue, smallestChildIndex);
	}
}

void heapifyUP(Priority_Queue* queue, int index) {
	if (index == 0) return;

	int parentIndex = get_parent_index(index);
	if (queue->heap[index].distance < queue->heap[parentIndex].distance) {
		swap(&queue->heap[index], &queue->heap[parentIndex]);
		heapifyUP(queue, parentIndex);
	}
}

heapNode extract_min(Priority_Queue* queue) {
	heapNode root = queue->heap[0];
	swap(&queue->heap[0], &queue->heap[queue->size - 1]);
	queue->size--;
	heapifyDOWN(queue, 0);

	return root;
}

void insert(Priority_Queue* queue, heapNode X) {
	queue->heap[queue->size++] = X;
	heapifyUP(queue, queue->size - 1);
}

void dijkstra(weightedGraph* graph) {
	queue = create_PriorityQueue(graph->edge_count + 1);
	distance = (int*)malloc((graph->node_count + 1) * sizeof(int));
	visited = (bool*)malloc((graph->node_count + 1) * sizeof(bool));

	for (int i = 1; i <= graph->node_count; i++) {
		distance[i] = INT_MAX;
		visited[i] = false;
	}
	heapNode source;
	source.distance = 0;
	source.node = 1;
	insert(queue, source);
	distance[1] = 0;

	while (queue->size > 0) {
		heapNode u = extract_min(queue);
		if (visited[u.node] == true)
			continue;
		visited[u.node] = true;
		for (weightedListNode* v = graph->adjacencyList[u.node]; v != NULL; v = v->next)
			if (visited[v->node] == false && distance[u.node] + v->weight < distance[v->node]) {
				distance[v->node] = distance[u.node] + v->weight;
				heapNode newNode;
				newNode.node = v->node;
				newNode.distance = distance[v->node];
				insert(queue, newNode);
			}
	}
}

void print_array(const char* fileName, int* array, int start, int finish) {
	FILE* output = fopen(fileName, "w");
	if (output == NULL) exit(2);

	for (int i = start; i <= finish; i++) {
		int val = (array[i] == INT_MAX) ? 0 : array[i];
		fprintf(output, "%d ", val);
	}

	fclose(output);
}