#include <stdio.h>
#include <stdlib.h>
#include <string>
using namespace std;
 
 
int matrixFloyd(int *C, int n, int *A, string* s)
{
 
  int i,j,k;
 
  
  for (i=0; i<n; i++)
  {
    for (j=0; j<n; j++)
    {
      if ( *(C+i*n+j) == -1)
      {
        *(A+i*n+j) = 999999999;
      }
      else
      {
        *(A+i*n+j) = 1;
        char sz[3]="";
        sprintf(sz,"%d",j+1);
        s[i*n+j]=sz;
      }
    }
  }
 
  
  for (i=0; i<n; i++)
  {
    *(A+i*n+i) = 0;
  }
 
  
  for (k=0; k<n; k++)
  {
    for (i=0; i<n; i++)
    {
      for (j=0; j<n; j++)
      {
        if ( *(A+i*n+k) + *(A+k*n+j) < *(A+i*n+j) )
        
          // A[i][j] = A[i][k] + A[k][j];
          *(A+i*n+j) = *(A+i*n+k)+ *(A+k*n+j);
      }
    }
  }
 
  return 0;
}    

void testFunction()
{
 
 
   int x, y;
  int n=5;
  int *C=new int[n*n];

C[0 ]=0;C[1 ]=2;C[2 ]=-1;C[3 ]=1;C[4 ]=8;
C[5 ]=6;C[6 ]=0;C[7 ]=3;C[8 ]=2;C[9 ]=-1;
C[10 ]=-1;C[11 ]=-1;C[12 ]=0;C[13 ]=4;C[14 ]=-1;
C[15 ]=-1;C[16 ]=-1;C[17 ]=2;C[18 ]=0;C[19 ]=3;
C[20 ]=3;C[21 ]=-1;C[22 ]=-1;C[23 ]=-1;C[24 ]=0;
 
 
  int* A = new int[n*n];
  string* s = new string[n*n];
  printf("Beginning matrix:\n");
  for(x=0;x<n;x++)
  {
    for(int y=0;y<n;y++)
    {
      printf("%d ",*(C+x*n+y));
    }
    printf("\n");
  }
 
 
  matrixFloyd(C,n,A,s);
 
  printf("Shortest distances:\n");
  for(x=0;x<n;x++)
  {
    for(y=0;y<n;y++)
    {
      printf("%d ",*(A+x*n+y));
    }
    printf("\n");
  }

    delete [] A;
    delete [] C;
    delete [] s;
 
} 
 
int main()
{
  testFunction();
  char c;
  scanf("%c",&c);
}