Cod sursa(job #944869)

Utilizator gabriel.badeaGabriel Badea gabriel.badea Data 29 aprilie 2013 22:03:53
Problema Floyd-Warshall/Roy-Floyd Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.73 kb
#include<iostream>
#include<stdio.h>
#define Nmax 101
using namespace std;

int N;
int a[Nmax][Nmax];
int main()
{
    freopen("royfloyd.in", "r", stdin);
    freopen("royfloyd.out", "w", stdout);

    cin >> N;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= N; ++j)
            cin >> a[i][j];
    for(int k = 1; k <= N; ++k)
        for(int i = 1; i <= N; ++i)
            for(int j = 1; j <= N; ++j)
                if(a[i][k] && a[i][j] && (a[i][j] > a[i][k] + a[k][j]) || !a[i][j]) && i != j)
                    a[i][j] = a[i][k] + a[k][j];

    for(int i = 1; i <= N; ++i)
    {
        for(int j = 1; j <= N; ++j)
            cout << a[i][j] << " ";
        cout << endl;
    }

    return 0;
}