#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);
}