/**
 * A Fibonacci heap, a graph with weighted edges, and dijkstra's algorithm
 *
 * Author: Erel Segal http://t...content-available-to-author-only...s.fm/rentabrain
 * Date: 2010-11-11
 */



#include <iostream>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <algorithm>
#include <vector>
using namespace std;

typedef unsigned int uint;



/* ------ PART A: Fibonacci Heap -------- */

void maximize (uint& a, uint b) {
	if (b>a)
		a = b;
}


/**
 * The heap is a min-heap sorted by Key.
 */
template <typename Data, typename Key> class FibonacciHeapNode {
	Key myKey;
	Data myData;

	uint degree; // number of childern. used in the removeMinimum algorithm.
	bool mark;   // mark used in the decreaseKey algorithm.
	
	FibonacciHeapNode<Data,Key>* previous;  // pointers in a circular doubly linked list
	FibonacciHeapNode<Data,Key>* next;
	FibonacciHeapNode<Data,Key>* child; // pointer to the first child in the list of children
	FibonacciHeapNode<Data,Key>* parent;

	FibonacciHeapNode() {}
	FibonacciHeapNode(Data d, Key k):
		myKey(k), 
		myData(d),
		degree(0),
		mark(false),
		child(NULL), 
		parent(NULL)
		{
			previous = next = this; // doubly linked circular list
	}
	
	bool isSingle() const {
		return (this == this->next);
	}

	// inserts a new node after this node
	void insert(FibonacciHeapNode<Data,Key>* other) {
		if (!other)
			return;

		// For example: given 1->2->3->4->1, insert a->b->c->d->a after node 3:
		//	result: 1->2->3->a->b->c->d->4->1

		this->next->previous = other->previous;
		other->previous->next = this->next;

		this->next = other;
		other->previous = this;
	}

	void remove() {
		this->previous->next = this->next;
		this->next->previous = this->previous;
		this->next = this->previous = this;
	}
	
	void addChild(FibonacciHeapNode<Data,Key>* other) { // Fibonacci-Heap-Link(other,current)
		if (!child)
			child = other;
		else
			child->insert(other);
		other->parent = this;
		other->mark = false;
		degree++;
	}

	void removeChild(FibonacciHeapNode<Data,Key>* other) {
		if (other->parent!=this)
			throw string ("Trying to remove a child from a non-parent");
		if (other->isSingle()) {
			if (child != other)
				throw string ("Trying to remove a non-child");
			child = NULL;
		} else {
			if (child == other)
				child = other->next;
			other->remove(); // from list of children
		}
		other->parent=NULL;
		other->mark = false;
		degree--;
	}

	
	friend ostream& operator<< (ostream& out, const FibonacciHeapNode& n) {
		return (out << n.myData << ":" << n.myKey);
	}
	
	void printTree(ostream& out) const {
		out << myData << ":" << myKey << ":" << degree << ":" << mark;
		if (child) {
			out << "(";
			const FibonacciHeapNode<Data,Key>* n=child;
			do {
				if (n==this)
					throw string("Illegal pointer - node is child of itself");
				n->printTree(out); 
				out << " ";
				n = n->next;
			} while (n!=child);
			out << ")";
		}
	}

	void printAll(ostream& out) const {
		const FibonacciHeapNode<Data,Key>* n=this;
		do {
			n->printTree(out); 
			out << " ";
			n = n->next;
		} while (n!=this);
		out << endl;
	}
	
public:
	Key key() const { return myKey; }
	Data data() const { return myData; }
	
	template <typename D, typename K> friend class FibonacciHeap;
}; // FibonacciHeapNode



template <typename Data, typename Key> class FibonacciHeap {
public:
	typedef FibonacciHeapNode<Data,Key>* PNode;
	
private:
	PNode rootWithMinKey; // a circular d-list of nodes
	uint count;      // total number of elements in heap
	uint maxDegree;  // maximum degree (=child count) of a root in the  circular d-list

protected:
	PNode insertNode(PNode newNode) {
		//if (debug) cout << "insert " << (*newNode) << endl;
		if (!rootWithMinKey) { // insert the first myKey to the heap:
			rootWithMinKey = newNode;
		} else {
			rootWithMinKey->insert(newNode);  // insert the root of new tree to the list of roots
			if (newNode->key() < rootWithMinKey->key())
				rootWithMinKey = newNode;
		}
		return newNode;
	}

public:
	bool debug, debugRemoveMin, debugDecreaseKey;

	FibonacciHeap(): 
		rootWithMinKey(NULL), count(0), maxDegree(0), debug(false), debugRemoveMin(false) {}

	~FibonacciHeap() { /* TODO: remove all nodes */ }

	bool empty() const {return count==0;}

	PNode minimum() const { 
		if (!rootWithMinKey)
			throw string("no minimum element");
		return rootWithMinKey;
	}

	void printRoots(ostream& out) const {
		out << "maxDegree=" << maxDegree << "  count=" << count << "  roots=";
		if (rootWithMinKey)
			rootWithMinKey->printAll(out);
		else
			out << endl;
	}

	void merge (const FibonacciHeap& other) {  // Fibonacci-Heap-Union
		rootWithMinKey->insert(other.rootWithMinKey);
		if (!rootWithMinKey || (other.rootWithMinKey && other.rootWithMinKey->key() < rootWithMinKey->key()))
			this->rootWithMinKey = other.rootWithMinKey;
		count += other.count;
	}
	
	PNode insert (Data d, Key k) {
		if (debug) cout << "insert " << d << ":" << k << endl;
		count++;
		// create a new tree with a single myKey:
		return insertNode(new FibonacciHeapNode<Data,Key>(d,k));
	}


	void removeMinimum() {  // Fibonacci-Heap-Extract-Min, CONSOLIDATE
		if (!rootWithMinKey)
			throw string("trying to remove from an empty heap");

		if (debug) cout << "removeMinimum " << (*rootWithMinKey) << endl;
		count--;

		/// Phase 1: Make all the removed root's children new roots:
		// Make all children of root new roots:
		if (rootWithMinKey->child) {
			if (debugRemoveMin) {
				cout << "  root's children: "; 
				rootWithMinKey->child->printAll(cout);
			}
			PNode c = rootWithMinKey->child;
			do {
				c->parent = NULL;
				c = c->next;
			} while (c!=rootWithMinKey->child);
			rootWithMinKey->child = NULL; // removed all children
			rootWithMinKey->insert(c);
		}
		if (debugRemoveMin) {
			cout << "  roots after inserting children: "; 
			printRoots(cout);
		}
		

		/// Phase 2-a: handle the case where we delete the last myKey:
		if (rootWithMinKey->next == rootWithMinKey) {
			if (debugRemoveMin) cout << "  removed the last" << endl;
			if (count!=0)
				throw string ("Internal error: should have 0 keys");
			rootWithMinKey = NULL;
			return;
		}

		/// Phase 2: merge roots with the same degree:
		vector<PNode> degreeRoots (maxDegree+1); // make room for a new degree
		fill (degreeRoots.begin(), degreeRoots.end(), (PNode)NULL);
		maxDegree = 0;
		PNode currentPointer = rootWithMinKey->next;
		uint currentDegree;
		do {
			currentDegree = currentPointer->degree;
			if (debugRemoveMin) {
					cout << "  roots starting from currentPointer: "; 
					currentPointer->printAll(cout);
					cout << "  checking root " << *currentPointer << " with degree " << currentDegree << endl;
			}

			PNode current = currentPointer;
			currentPointer = currentPointer->next;
			while (degreeRoots[currentDegree]) { // merge the two roots with the same degree:
				PNode other = degreeRoots[currentDegree]; // another root with the same degree
				if (current->key() > other->key())
					swap(other,current); 
				// now current->key() <= other->key() - make other a child of current:
				other->remove(); // remove from list of roots
				current->addChild(other);
				if (debugRemoveMin) cout << "  added " << *other << " as child of " << *current << endl;
				degreeRoots[currentDegree]=NULL;
				currentDegree++;
				if (currentDegree >= degreeRoots.size())
					degreeRoots.push_back((PNode)NULL);
			}
			// keep the current root as the first of its degree in the degrees array:
			degreeRoots[currentDegree] = current;
		} while (currentPointer != rootWithMinKey);

		/// Phase 3: remove the current root, and calcualte the new rootWithMinKey:
		delete rootWithMinKey;
		rootWithMinKey = NULL;

		uint newMaxDegree=0;
		for (uint d=0; d<degreeRoots.size(); ++d) {
			if (debugRemoveMin) cout << "  degree " << d << ": ";
			if (degreeRoots[d]) {
				if (debugRemoveMin) cout << " " << *degreeRoots[d] << endl;
				degreeRoots[d]->next = degreeRoots[d]->previous = degreeRoots[d];
				insertNode(degreeRoots[d]);
				maximize(newMaxDegree,d);
			} else {
				if (debugRemoveMin) cout << "  no node" << endl;
			}
		}
		maxDegree=newMaxDegree;
	}
	
	void decreaseKey(PNode node, Key newKey) {
		if (newKey > node->myKey)
			throw string("Trying to decrease key to a greater key");
		else if (newKey == node->myKey)
			return; // nothing to do

		if (debug) cout << "decrease key of " << *node << " to " << newKey << endl;
		// Update the key and possibly the min key:
		node->myKey = newKey;

		// Check if the new key violates the heap invariant:
		PNode parent = node->parent;
		if (!parent) { // root node - just make sure the minimum is correct
			if (newKey < rootWithMinKey->key())
				rootWithMinKey = node;
			return; // heap invariant not violated - nothing more to do
		} else if (parent->key() <= newKey) {
			return; // heap invariant not violated - nothing more to do
		}

		for(;;) {
			parent->removeChild(node);
			insertNode(node);
			if (debugDecreaseKey) {
				cout << "  removed " << *node << " as child of " << *parent << endl;
				cout << "  roots after remove: "; 
				rootWithMinKey->printAll(cout);
			}

			if (!parent->parent) { // parent is a root - nothing more to do
				break;
			} else if (!parent->mark) {  // parent is not a root and is not marked - just mark it
				parent->mark = true;
				break;
			} else {
				node = parent;
				parent = parent->parent;
				continue;
			}
		};
	}

	void remove(PNode node, Key minusInfinity) {
		if (minusInfinity >= minimum()->key())
			throw string("2nd argument to remove must be a key that is smaller than all other keys");
		decreaseKey(node, minusInfinity);
		removeMinimum();
	}

	static int UnitTest() {
		try {
		typedef FibonacciHeap<string, uint> FibHeap;
		FibHeap h;
		h.debug=true;
		h.debugRemoveMin=false;
		h.debugDecreaseKey = false;

		h.insert("a",4);
		h.insert("b",2);
		h.insert("c",7);
		h.insert("d",5);
		h.insert("e",1);
		h.insert("f",8);
		h.printRoots(cout);

		while (!h.empty()) {
			cout << "min=" << *h.minimum() << endl;
			h.removeMinimum(); 
			h.printRoots(cout);
		}

		cout << endl << endl;

		vector <FibHeap::PNode> nodes(6);
		nodes[0] = 
			h.insert("a",400);
		nodes[1] = 
			h.insert("b",200);
		nodes[2] = 
			h.insert("c",70);
		nodes[3] = 
			h.insert("d",50);
		nodes[4] = 
			h.insert("e",10);
		nodes[5] = 
			h.insert("f",80);
		h.printRoots(cout);
		cout << "min=" << *h.minimum() << endl;

		h.removeMinimum(); 
		cout << "min=" << *h.minimum() << endl;
			nodes[4]=NULL;
		h.printRoots(cout);

		for (uint i=0; i<nodes.size(); ++i) {
			if (!nodes[i]) // minimum - already removed
				continue;
			h.decreaseKey(nodes[i], nodes[i]->key()/10);
			cout << "min=" << *h.minimum() << endl;
			h.printRoots(cout);
		}

		cout << endl << endl;
		
		h.insert("AA",4);
		h.insert("BB",2);
		h.insert("CC",7);
		h.insert("DD",5);
		h.insert("EE",1);
		h.insert("FF",8);
		h.printRoots(cout);

		while (!h.empty()) {
			cout << "min=" << *h.minimum() << endl;
			h.removeMinimum(); 
			h.printRoots(cout);
		}

		cout << endl << endl;
		return 0;

		} catch (string s) {
			cerr << endl << "ERROR: " << s << endl;
			return 1;
		}
	}

};  // FibonacciHeap







/* ------ PART B: Graph with weighted edges -------- */

typedef map<uint,int> AdjacencyListWithWeights; // matches a target vertex to a weight.
const uint MAXINT = 999999999u;

template <class Iterator> ostream& print (Iterator iFrom, Iterator iTo) {
	for (; iFrom!=iTo; ++iFrom) cout << *iFrom << " ";
	return (cout << endl);
}

template <class T> ostream& operator<< (ostream& out, const vector<T>& theVector) {
	return print (theVector.begin(), theVector.end());
}

template <class T> ostream& operator<< (ostream& out, const set<T>& theVector) {
	return print (theVector.begin(), theVector.end());
}



/**
 * A graph where the vertices are integers; stores edges in adjacency list.
 */
class GraphWithWeights {
	vector<AdjacencyListWithWeights> myVertices;

public:
	GraphWithWeights (uint nVertices): myVertices(nVertices) {}
	uint size() const { return myVertices.size(); }

	GraphWithWeights& addEdge (uint iFrom, uint iTo, uint weight) {
		if (iFrom >= size()) {
			throw string("trying to add an edge from a nonexisting vertex index");
		}
		if (iTo >= size()) {
			throw string("trying to add an edge to a nonexisting vertex index");
		}
		myVertices[iFrom][iTo] = weight;
		return *this;
	}

	void createClique() {     // for testing
		for (uint iFrom=0; iFrom<size(); ++iFrom) {
			for (uint iTo=0; iTo<size(); ++iTo) {
				if (iFrom!=iTo)
					addEdge(iFrom,iTo, (iFrom-iTo)*(iFrom-iTo));
			}
		}
	}

	void printOutgoingEdges(uint iFrom, ostream& out) const {
		out << iFrom << " -> ";
		const AdjacencyListWithWeights& targets = myVertices[iFrom];
		AdjacencyListWithWeights::const_iterator f;
		for (f=targets.begin(); f!=targets.end(); ++f) {
			out << " " << f->first << ":" << f->second;
		}
		out << endl;
	}

	void printIncomingEdges(uint iTo, ostream& out) {
		out << iTo << " <- ";
		for (uint iFrom=0; iFrom<myVertices.size(); ++iFrom) {
			const AdjacencyListWithWeights& currentTargets = myVertices[iFrom];
			AdjacencyListWithWeights::const_iterator it = currentTargets.find(iTo);
			if (it != currentTargets.end()) {
				out << " " << iFrom << ":" << it->second;
			}
		}
		out << endl;
	}

	// Print the graph, using the vertex indices
	void printIndices(ostream& out) const {
		for (uint i=0; i<size(); ++i)
			printOutgoingEdges (i, out);
	}

	friend ostream& operator<< (ostream& out, const GraphWithWeights& g) {
		g.printIndices(out);
		return out;
	}
	

	/// @see http://w...content-available-to-author-only...t.org/doc/libs/1_44_0/libs/graph/doc/dijkstra_shortest_paths_no_color_map.html
	void shortest_paths(uint source, vector<uint>& distances, vector<uint>& previous) const {
		typedef FibonacciHeap<uint, uint> VertexQueue; 
			// Data=vertex, Key=distance from source
		VertexQueue vertexQueue;
		//vertexQueue.debug = true;

		distances.resize(size());
		previous.resize(size());
		vector<VertexQueue::PNode> vertexData(size()); // pointers to the inside the vertex queue, for decrease-key

		fill(distances.begin(), distances.end(), MAXINT);
		fill(previous.begin(), previous.end(), MAXINT);
		fill(vertexData.begin(), vertexData.end(), (VertexQueue::PNode)NULL);

		// Initlaize source:
		previous[source] = MAXINT;
		distances[source] = 0;
		vertexData[source] = vertexQueue.insert(source, 0);

		// Loop over all vertices:
		while (!vertexQueue.empty()) {
			VertexQueue::PNode current = vertexQueue.minimum();     // finish a vertex
			uint currentVertex   = current->data();
			uint currentDistance = current->key();
			vertexQueue.removeMinimum();

			// Loop over all outgoing edges of the current vertex:
			const AdjacencyListWithWeights& nextTargets = myVertices[currentVertex];
			AdjacencyListWithWeights::const_iterator iNeighbour;
			for (iNeighbour=nextTargets.begin(); iNeighbour!=nextTargets.end(); ++iNeighbour) {
				uint neighbour = iNeighbour->first;
				uint distanceFromCurrentToNeighbour = iNeighbour->second;
				uint newDistanceToNeighbour = currentDistance + distanceFromCurrentToNeighbour;
				//cout << "  visiting edge to " << neighbour << " with distance " << distanceFromCurrentToNeighbour 
				//	<< " new distance " << newDistanceToNeighbour << " old distance " << distances[neighbour] << endl;
				if (newDistanceToNeighbour < distances[neighbour]) {   // a tree edge
					distances[neighbour] = newDistanceToNeighbour;
					previous[neighbour] = currentVertex;
					if (vertexData[neighbour]) {
						vertexQueue.decreaseKey(vertexData[neighbour], newDistanceToNeighbour);
					}
				}
				if (!vertexData[neighbour]) {
					vertexData[neighbour] = vertexQueue.insert(neighbour, newDistanceToNeighbour);
				}
			}
		}
	}
	
	
	void print_shortest_paths_from(uint iFrom) {
		vector<uint> distances, previous;
		shortest_paths(iFrom, distances, previous);
		cout << "Dijkstra from " << iFrom << ": " << endl << "distances: " << distances << "previouses: " << previous << endl;
	}
}; // end of class GraphWithWeights



int main() {

/*
	GraphWithWeights g(12);
	g.addEdge(0,1, 11).addEdge(1,2, 12).addEdge(0,2, 24);
	g.addEdge(3,4, 11).addEdge(4,5, 12).addEdge(3,5, 22);
	g.addEdge(8,7, 11).addEdge(7,6, 12).addEdge(8,6, 24);
	g.addEdge(11,10, 11).addEdge(10,9, 12).addEdge(11,9, 22);
	cout << g << endl;
	g.printIncomingEdges(0,cout);
	g.printIncomingEdges(1,cout);
	g.printIncomingEdges(2,cout);
	g.printIncomingEdges(3,cout);
	g.printIncomingEdges(4,cout);
	cout << endl;

	g.print_shortest_paths_from(0); // shortest distance to 2 should be 23
	g.print_shortest_paths_from(3); // shortest distance to 5 should be 22
	g.print_shortest_paths_from(8); // shortest distance to 6 should be 23
	g.print_shortest_paths_from(11); // shortest distance to 9 should be 23
	return 1;
*/
	cout << "Enter number of nodes: ";
	uint nodeCount;
	cin >> nodeCount;
	GraphWithWeights clique(nodeCount);
	clique.createClique();
	if (nodeCount<=10)
		cout << clique << endl;
	//for (uint i=0; i<5; ++i)
	//	clique.print_shortest_paths_from(i);

	time_t before = time(NULL);
	clique.print_shortest_paths_from(clique.size()/4);
	time_t after = time(NULL);
	cout << "time for a single calculation = " << (after-before) << " seconds" << endl;

}