Cod sursa(job #1480606)

Utilizator laurageorgescuLaura Georgescu laurageorgescu Data 2 septembrie 2015 21:10:41
Problema Floyd-Warshall/Roy-Floyd Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include<fstream>

using namespace std;

ifstream fin( "royfloyd.in" ); ofstream fout( "royfloyd.out" );

const int nmax = 100;
int d[ nmax + 1 ][ nmax + 1 ];

int main() {
    int n;
    fin >> n;
    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            fin >> d[ i ][ j ];
        }
    }
    for( int k = 1; k <= n; ++ k ) {
        for( int i = 1; i <= n; ++ i ) {
            for( int j = 1; j <= n; ++ j ) {
                if ( d[ i ][ k ] && d[ k ][ j ] && i != j && (d[ i ][ j ] > d[ i ][ k ] + d[ k ][ j ] || !d[ i ][ j ])) {
                    d[ i ][ j ] = d[ i ][ k ] + d[ k ][ j ];
                }
            }
        }
    }

    for( int i = 1; i <= n; ++ i ) {
        for( int j = 1; j <= n; ++ j ) {
            fout << d[ i ][ j ] << " ";
        }
        fout << "\n";
    }
    fin.close();
    fout.close();
    return 0;
}