/**
	Алгоритмите на Прим и Дийкстра с Binary Heap и Decrease Key (разгледайте minHeap.h)
*/

#include <iostream>
#include <vector>
#include "minHeap.h"
#define Inf 2000000000
using namespace std;

typedef pair <int, int> pr;

const int n = 8;

vector <pr> graph[n] = {
	{ pr(1, 1), pr(3, 3), pr(4, 5) },
	{ pr(0, 1), pr(2, 2), pr(5, 2) },
	{ pr(1, 2), pr(4, 6) },
	{ pr(0, 3), pr(6, 10) },
	{ pr(0, 5), pr(2, 6), pr(6, 7), pr(7, 2) },
	{ pr(1, 2), pr(7, 5) },
	{ pr(3, 10), pr(4, 7), pr(7, 20) },
	{ pr(4, 2), pr(5, 5), pr(6, 20) } };

bool finalized[n];
int dist[n];
int key[n];
int parent[n];

int MST_Prim(int s)
{
	for (int i = 0; i < n; i++){ key[i] = Inf; finalized[i] = false; parent[i] = -1; }
	key[s] = 0;

	int sum = 0;
	minHeap q(n, key);
	
	while (!q.empty())
	{
		int u = q.extract_min().second;
		
		if (key[u] == Inf) return sum;
		finalized[u] = true;

		sum += key[u];

		for (pr e : graph[u])
		{
			int v = e.first, w = e.second;
			if (!finalized[v] && w < key[v])
			{
				key[v] = w;
				parent[v] = u;
				q.decrease_key(v, key[v]);
			}
		}
	}
	return sum;
}

void Dijkstra(int s)
{
	for (int i = 0; i < n; i++){ dist[i] = Inf; finalized[i] = false; parent[i] = -1; }
	dist[s] = 0;

	minHeap q(n, dist);

	while (!q.empty())
	{
		int u = q.extract_min().second;
		
		if (dist[u] == Inf) return;
		finalized[u] = true;

		for (pr e : graph[u])
		{
			int v = e.first, w = e.second;
			if (!finalized[v] && w + dist[u] < dist[v])
			{
				dist[v] = w + dist[u];
				parent[v] = u;
				q.decrease_key(v, dist[v]);
			}
		}
	}
}

int main()
{
	Dijkstra(0);

	for (int i = 0; i < n; i++) if (dist[i] != Inf)cout << dist[i] << " "; else cout << "INF ";
	cout << endl;

	return 0;
}