#include <stdlib.h>
#include<stdio.h>
using namespace std;

int **matr_cost,**drum,x[100],num_nodes;

void generare()
{
	printf("%s ","Introduceti numarul de noduri");
	scanf("%d ",&num_nodes);
	matr_cost = (int**) malloc(num_nodes*sizeof(int*));
	for(int i = 0; i < num_nodes; i++) 
		matr_cost[i] = (int*) malloc(num_nodes*sizeof(int));
	
	drum = (int**) malloc(num_nodes*sizeof(int*));
	for(int i = 0; i < num_nodes; i++) 
		drum[i] = (int*) malloc(num_nodes*sizeof(int));
	
	for(int i = 0; i < num_nodes; i++) 
		for(int j = 0; j < num_nodes; j++)
			if(i != j)
				matr_cost[i][j] = rand()%10;
			  else matr_cost[i][j] = 0;
	for(int i = 0; i < num_nodes; i++) 
		for(int j = 0; j < num_nodes; j++)
			if(matr_cost[i][j] == 0 && i!=j)
				matr_cost[i][j] = 10000;//acolo unde nu exista drum
	for(int i = 0; i < num_nodes; i++)
		 for(int j = 0; j < num_nodes; j++) {
			 if(i != j && matr_cost[i][j] != 10000) 
				 drum[i][j] = i;
		 }
	for(int i = 0; i < num_nodes; i++) {
		for(int j = 0; j < num_nodes; j++)
			printf("%d ",matr_cost[i][j]);	 
        printf("\n");
	}
}


void roy_floyd()
{ 
	for(int k = 0; k < num_nodes; k++)
		 for(int i = 0; i < num_nodes; i++)
			for(int j = 0; j < num_nodes; j++)
			   if((matr_cost[i][k] != 10000 ) && ( matr_cost[k][j] != 10000 ))
				 if(matr_cost[i][j] > matr_cost[i][k] + matr_cost[k][j]) {
					 matr_cost[i][j] = matr_cost[i][k] + matr_cost[k][j] ;
					 drum[i][j] = drum[k][j]; 
				 }

}

void druum(int i,int j)
{ if(i != j)
    { int k = drum[i][j];
      druum(i,k);
      printf("%d ",k);
	}
}

void afisare()
{ 	
	for(int i = 0; i < num_nodes; i++)
		 for(int j = 0; j < num_nodes; j++)
			if(i != j && matr_cost[i][j] != 10000) {
				printf("%s %d %s %d %s %d \n","Costul drumului minim de la ",i," la ",j," este ",matr_cost[i][j]);
                druum(i,j);
                printf("%d  \n",j);
			}
             else 
				 printf("%s %d %s %d \n","Nu este drum de la ",i," la ",j);
}

int main()
{ generare();
  roy_floyd();
  afisare(); 
  return 0;
}