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

#include "priority_queue1.h"
#include "record_routes.h"

using namespace std;

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

struct Graph {
	int num_connections;
	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;
		}
		cout << "Graph initialize established.";
	}
	else
		cout << "Graph not established. No memory available.\n\n";


	FILE *cfPtr;
	if( (cfPtr = fopen("1.txt", "r")) == NULL)
		cout << "File couldn't be opened\n";
	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].num_connections, 
				&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);

		cout << "Graph establish.\n";
	}

	priority_queue1 q;
	record_routes r(nodecount);

	int sum;
	while( !q.isEmpty() ) {
		for(i = 0; i<myGraph[q.top()].num_connections; i++) {
			sum = myGraph[q.top()].shortestDistance + myGraph[q.top()].edges[i].weight;
			if(myGraph[myGraph[q.top()].edges[i].dest].shortestDistance > sum) {
				myGraph[myGraph[q.top()].edges[i].dest].shortestDistance = sum;
				r.record( q.top(),  myGraph[q.top()].edges[i].dest );
				q.push(myGraph[q.top()].edges[i].dest);
			}
		}

		q.pop();
	}

	for(i=0; i<nodecount; i++) {
		r.printRoutes(i);
		cout << "Shortest distance is " << myGraph[i].shortestDistance << "\n\n";
	}

	cout << endl;

	return 0;
}