#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 num_connections;
	int shortestDistance;
	int prevPath;
	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].prevPath = -1;
		}
		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_queue <int, vector<int>, greater<int> > q;

	q.push( 0 );

	int top = -1, sum;
	while( !q.empty( ) ) {
		if( top == q.top( ) ) {
			q.pop( );
		}
		else {
			top = q.top( );
			for(i = 0; i<myGraph[top].num_connections; i++) {
				sum = myGraph[top].shortestDistance + myGraph[top].edges[i].weight;
				if(myGraph[myGraph[top].edges[i].dest].shortestDistance > sum) {
					myGraph[myGraph[top].edges[i].dest].shortestDistance = sum;
					myGraph[myGraph[top].edges[i].dest].prevPath = top;

					if( top == q.top() )
						q.pop();

					q.push(myGraph[top].edges[i].dest);
				}
			}
		}
	}

	cout << endl;
	for(i=0; i<nodecount; i++) {
		if(myGraph[i].prevPath == -1)
			cout << "Shortest path from node \'0\' to node \'" << i << "\' is not yet being found\n";
		else {
			cout << "Shortest path from node \'0\' to node \'" << i << "\':\n"
				<< i << " --> ";
			int preRoute = myGraph[i].prevPath;
			while(preRoute != -1) {
				cout << preRoute << " --> ";
				preRoute = myGraph[preRoute].prevPath;
			}
			cout << "End\n";
		}

		cout << "Shortest distance is " << myGraph[i].shortestDistance << "\n\n";
	}

	cout << endl;

	return 0;
}