# include <iostream>
# include <fstream>
# define INF 10000
void read_data ( std :: istream & , int & ) ;
void read_matrix ( std :: istream & , int **, int ) ;
void print_matrix ( std :: ostream & , int ** , int ) ;
void free_matrix ( int ** , int ) ;
void royfloyd ( std :: ostream & , int ** , int ) ;
int main () {
std :: ifstream f ("royfloyd.in" ) ;
std :: ofstream g ("royfloyd.out" ) ;
int N ;
int **values = NULL ;
read_data ( f , N ) ;
values = new int * [N] ;
for ( int i = 0 ; i < N ; i ++ ) {
values[i] = new int [N] ;
}
read_matrix ( f , values , N ) ;
royfloyd ( g , values , N ) ;
free_matrix ( values , N ) ;
f.close () ;
g.close () ;
return 0 ;
}
void royfloyd ( std :: ostream & g , int ** values , int N ) {
int ** final_matrix = new int * [N] ;
for ( int i = 0 ; i < N ; i ++ ) {
final_matrix[i] = new int [N] ;
}
for ( int i = 0 ; i < N ; i ++ ) {
for ( int j = 0 ; j < N ; j ++ ) {
if ( i == j ) {
final_matrix[i][j] = 0 ;
} else if ( values[i][j] == 0 ) {
final_matrix[i][j] = INF ;
} else {
final_matrix[i][j] = values[i][j] ;
}
}
}
for ( int k = 1 ; k < N ; k ++ ) {
for ( int i = 0 ; i < N ; i ++ ) {
for ( int j = 0 ; j < N ; j ++ ) {
if ( final_matrix[i][j] > final_matrix[i][k] + final_matrix[k][j] ) {
final_matrix[i][j] = final_matrix[i][k] + final_matrix[k][j] ;
}
}
}
}
print_matrix ( g , final_matrix , N ) ;
free_matrix ( final_matrix , N ) ;
}
void free_matrix ( int ** matrix , int N ) {
for ( int i = 0 ; i < N ; i ++ ) {
delete [] matrix[i] ;
}
delete [] matrix ;
}
void read_data ( std :: istream & f , int & N ) {
f >> N ;
}
void read_matrix ( std :: istream & f , int ** matrix , int N ) {
for ( int i = 0 ; i < N ; i ++ ) {
for ( int j = 0 ; j < N ; j ++ ) {
f >> matrix[i][j] ;
}
}
}
void print_matrix ( std :: ostream & g , int ** matrix , int N ) {
for ( int i = 0 ; i < N ; i ++ ) {
for ( int j = 0 ; j < N ; j ++ ) {
if ( matrix[i][j] == INF ) {
g << "0 " ;
} else {
g << matrix[i][j] << ' ' ;
}
}
g << '\n' ;
}
}
Grosu Codrut-Cristian codrut_grosu