Cod sursa(job #1976868)

Utilizator taigi100Cazacu Robert taigi100 Data 4 mai 2017 13:42:55
Problema Floyd-Warshall/Roy-Floyd Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.02 kb
/*
    Keep It Simple!
*/
#include <fstream>

using namespace std;

const int MAX_N = 101;
const int oo = 1 << 29;


int ad[MAX_N][MAX_N];
int dist[MAX_N][MAX_N];
int N;

void ReadInput() {
    ifstream f("royfloyd.in");
    f >> N;
    for (int i = 1; i <= N; ++i)
        for (int j = 1; j <= N; ++j) {
            f >> ad[i][j];
            dist[i][j] = ad[i][j];
            if (!ad[i][j] && i != j)
                dist[i][j] = oo;
        }
}

void ComputeRF() {
    for (int k = 1; k <= N; ++k)
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                if (dist[i][j] > dist[i][k] + dist[k][j] && i != j)
                    dist[i][j] = dist[i][k] + dist[k][j];

}

void Solve() {
    ReadInput();
    ComputeRF();

    ofstream g("royfloyd.out");
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j)
            g << (dist[i][j] == oo ? 0 : dist[i][j]) << " ";
        g << '\n';
    }
}

int main()
{
    Solve();
    return 0;
}