#include<iostream.h>

#define MAX 10

class dijkstra
{
	private : int cost[MAX][MAX], d[MAX], p[MAX], visited[MAX];
		  int n;
	public  : void readmatrix();
		  void shortpath(int);
		  void display(int);
};

void dijkstra :: readmatrix()
{
	int i, j;
	cout << "\nEnter the number of vertices in the Graph : ";
	cin  >> n;
	cout << "\nEnter the Cost matrix of the Graph\n\n";
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			cin >> cost[i][j];
}

void dijkstra :: shortpath(int src)
{
	int i, j, min, u, v;
	for (i = 1; i <= n; i++)
	{
		d[i] = cost[src][i];
		visited[i] = 0;
		p[i] = src;
	}
	visited[src] = 1;
	for (i = 1; i <= n; i++)
	{
		min = 999;
		u = 0;
		for (j = 1; j <= n; j++)
		{
			if (!visited[j])
				if (d[j] < min)
				{
					min = d[j];
					u = j;
				}
		}
		visited[u] = 1;
		for (v = 1; v <= n; v++)
			if (!visited[v] && (d[u] + cost[u][v] < d[v]))
			{
				d[v] = d[u] + cost[u][v];
				p[v] = u;
			}
	}
}

void dijkstra :: display(int src)
{
	int i, k, parent;
	for (i = 1; i <= n; i++)
	{
		if (i == src)
			continue;
		cout << "\nThe Shortest Path from " << src << "to " << i << "is : ";
		k = i;
		cout << k << " <- ";
		while (p[k] != src)
		{
			cout << p[k] << " <- ";
			k = p[k];
		}
		cout << src;
		cout << " and the cost is : " << d[i] << endl;
	}
}

int main()
{
	int source;
	dijkstra dij;
	dij.readmatrix();
	cout << "\nEnter the Source : ";
	cin  >> source;
	dij.shortpath(source);
	dij.display(source);
	return 0;
}