#include <stdio.h>
#include <iostream>
#include <limits>
#include <malloc.h>

#include <queue>
#include <vector>
#include <deque>
#include <list>

using namespace std;

#define INFINITY numeric_limits<int>::max( )

struct Graph {
	int Name;
	int numberofPtrs;
	int shortestDistance;
	struct {
		int weight;
		int dest;
	} edges[5];
};

typedef struct Graph graph;
typedef graph *graphPtr;


int main()
{
	int nodecount = 30, i;
	graphPtr myGraph;

	myGraph = (graphPtr)calloc(nodecount, sizeof(graph));

	if(myGraph != NULL) {
		for(i=0; i<nodecount; i++) {
			if(i == 0)
				myGraph[i].shortestDistance = 0;
			else
				myGraph[i].shortestDistance = INFINITY;
			myGraph[i].Name = i;
		}
		cout << "Graph initialize established. Node 2 distance is " << myGraph[2].shortestDistance << endl;
	}
	else
		cout << "Graph not established. No memory available.\n\n" << endl;


	FILE *cfPtr;
	if( (cfPtr = fopen("1.txt", "r")) == NULL)
		cout << "File couldn't be opened\n" << endl;
	else {
	//build the graph
		for(i=0; i<nodecount-1; i++)
			fscanf(cfPtr, "%d%d%d%d%d%d%d%d%d%d%d", &myGraph[i].numberofPtrs, 
				&myGraph[i].edges[0].dest, &myGraph[i].edges[0].weight, 
				&myGraph[i].edges[1].dest, &myGraph[i].edges[1].weight, 
				&myGraph[i].edges[2].dest, &myGraph[i].edges[2].weight, 
				&myGraph[i].edges[3].dest, &myGraph[i].edges[3].weight, 
				&myGraph[i].edges[4].dest, &myGraph[i].edges[4].weight);
		fclose(cfPtr);

		printf("Graph establish.\n");
		printf("Node 10: %d %d %d %d %d %d %d %d %d %d %d\n", myGraph[10].numberofPtrs,
				myGraph[10].edges[0].dest, myGraph[10].edges[0].weight, 
				myGraph[10].edges[1].dest, myGraph[10].edges[1].weight, 
				myGraph[10].edges[2].dest, myGraph[10].edges[2].weight, 
				myGraph[10].edges[3].dest, myGraph[10].edges[3].weight, 
				myGraph[10].edges[4].dest, myGraph[10].edges[4].weight);
	}

//Initialize priority queue
	priority_queue <int, vector<int>, greater<int> > q;
	for(i =0; i<nodecount; i++)
		q.push(i);
//Initialize priority queue

	int currNode, sum;
	while( !q.empty( ) ) {
		currNode = q.top();
		q.pop();
		for(i = 0; i<myGraph[currNode].numberofPtrs; i++) {
			sum = myGraph[currNode].shortestDistance + myGraph[currNode].edges[i].weight;
			if(myGraph[myGraph[currNode].edges[i].dest].shortestDistance > sum) {
				myGraph[myGraph[currNode].edges[i].dest].shortestDistance = sum;
				q.push(myGraph[currNode].edges[i].dest);
			}
		}
	}

	return 0;
}