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

#define inf 20001

typedef struct graphMatrix {
	int** costMatrix;
	int numNodes;
} graphMatrix;

graphMatrix readGraphMatrix(const char* fileName)
{
	graphMatrix graph;
	int numEdges;

	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return graph;
	fscanf(f, "%d %d\n", &(graph.numNodes), &(numEdges));
	for (int i = 0; i < graph.numNodes; i++) {
		for (int j = 0; j < graph.numNodes; j++) {
			graph.costMatrix[i][j] = inf;
		}
	}
	graph.costMatrix = (int**)malloc(sizeof(int*) * graph.numNodes);
	int a, b, c;
	for (int i = 0; i < numEdges; i++) {
		fscanf(f, "%d %d %d\n", &a, &b, &c);
		graph.costMatrix[a - 1][b - 1] = c;
	}
	//TODO

	fclose(f);
	return graph;
}

typedef struct nodeDP {
	int node;
	int d;
	int parent;
} nodeDP;

int cmpNDP(const void* a, const void* b)
{
	nodeDP* A = (nodeDP*)a;
	nodeDP* B = (nodeDP*)b;
	if ((A->d - B->d) == 0)
		return (A->node - B->node);
	else
		return (A->d - B->d);
}

void printNDP(nodeDP* NDP, int n)
{
	printf("  Node: ");
	for (int i = 0; i < n; i++)
		printf("%5i", NDP[i].node + 1);
	printf("\n");
	printf("     D: ");
	for (int i = 0; i < n; i++)
		printf("%5i", NDP[i].d);
	printf("\n");
	printf("Parent: ");
	for (int i = 0; i < n; i++)
		printf("%5i", NDP[i].parent + 1);
	printf("\n");
}

nodeDP* dijsktra(graphMatrix graph, int source)
{
	nodeDP* NDP = (nodeDP*)malloc(sizeof(nodeDP) * graph.numNodes);
	if (NDP == NULL)
		return NULL;
	for (int i = 0; i < graph.numNodes; i++) {
		NDP[i].node = i;
		NDP[i].d = inf;
		NDP[i].parent = -1;
	}
	NDP[source].d = 0;
	int position = 0;
	qsort(NDP, graph.numNodes, sizeof(nodeDP), cmpNDP);

	do {
		for (int i = 0; i < graph.numNodes; i++) {
			if (NDP[position].d != inf && NDP[i].d > NDP[position].d + graph.costMatrix[NDP[position].node][NDP[i].node]) {
				NDP[i].d = NDP[position].d + graph.costMatrix[NDP[position].node][NDP[i].node];
				NDP[i].parent = NDP[position].node;
			}
		}
		qsort(NDP, graph.numNodes, sizeof(nodeDP), cmpNDP);
		position++;
	} while (position < graph.numNodes);
	//TODO
	//Helper for sort: qsort(NDP, graph.numNodes, sizeof(nodeDP), cmpNDP);
	return NDP;
}

int main()
{
	graphMatrix graphM = readGraphMatrix("dijsktra.in");
	nodeDP* NDP = dijsktra(graphM, 0);
	printf("\nDijsktra rezult:\n");
	printNDP(NDP, graphM.numNodes);
	return 0;
}