#include   <stdio.h>
#include   <dos.h>
#include   <conio.h>
#include   <iostream.h>


void calcpdn(int n);
void showvs(int,int);

int c[4][4];
int p[4][4];
int d[4][4];

int main(void)
{
 int n ;
 struct  time start,end;
  clrscr();
	printf("\nPlease Enter the n:");
	scanf("%d",&n);
	for (int i=0;i<n;i++)
	  for(int j=0;j<n;j++)
	{
	  printf("\nPlease Enter The P[%d,%d]:",i,j);
	  scanf("%d",&c[i][j]);
	}
	gettime(&start);
	calcpdn(n);
	gettime(&end);
	    int s,ms ;
    if(end.ti_sec>start.ti_sec) s =end.ti_sec-start.ti_sec ;
    else s = start.ti_sec-end.ti_sec    ;
    if(end.ti_hund>start.ti_hund) ms= end.ti_hund-start.ti_hund ;
    else ms =start.ti_hund-end.ti_hund  ;

    printf("\n\n\nThe Differ Time %d:%d",
	s,ms);
	  printf("\n\n\nFor Exit enter i=-1\n");
	  while (1)
	  { printf("\n\nPlease Enter the raseh i =");
	    scanf("%d",&i);
	    printf("\n\nPlease Enter the raseh j =");
	    scanf("%d",&j);
	    if (i == -1) break ;

	   if (p[i][j] != -1 ){
	      printf("\n\naz %d =====>> %d kotahtarin masir gozar az rashyae zir mibashad : ",i,j);
	      showvs(i,j);
	      } else
		printf("\n\naz  %d =====>> %d  kotahtrain masir   masir mostaghim mibashad : ",i,j);
	   }



  getch();
  return 0;
}
void calcpdn (int n)
{
     for(int i =0;i<n;i++)
	for(int j=0;j<n;j++)
	 {
	   p[i][j] = -1;
	   d[i][j] = c[i][j] ;
	 }
     for (int k=0 ; k<n ; k++)
       for(i=0 ; i<n ; i++)
	 for(j=0;j<n;j++)
	  {delay(50);
	   int dk = d[i][k] + d[k][j] ;
	   if (d[i][j] > dk)
	   {
	      d[i][j] = dk ;
	      p[i][j] = k;
	   }
	  }
}
void showvs (int i ,int j)
{int k;
 if (p[i][j] == -1) return ;
 k =p[i][j] ;
 showvs(i,k);
 cout << k << "\t";
 showvs(k,j);
}