Cerința

Se dă un graf orientat ponderat cu n noduri și m arce – în care fiecare arc are asociat un cost, număr natural strict pozitiv. Folosind algoritmul Roy-Floyd, construiți matricea costurilor minime, a[i][j] fiind costul minim al unui drum de la i la j, dacă există un asemenea drum, sau -1 în caz contrar.

Date de intrare

Fișierul de intrare roy-floyd.in conține pe prima linie numerele n m, iar următoarele linii câte un triplet i j c, cu semnificația: există arcul (i j) și are costul c.

Date de ieșire

Fișierul de ieșire roy-floyd.out va conține matricea construită, câte o linie a matricei pe o linie a fișierului, elementele de pe fiecare linie fiind separate prin exact un spațiu.

Restricții și precizări

• 1 ≤ n ≤ 100
• costul unui arc va fi mai mic decât 1000
• costul unui drum este egal cu suma costurilor arcelor care îl compun

Exemplu

roy-floyd.in

5 6
1 3 1
2 1 2
4 2 1
4 3 8
5 3 5
5 4 2

roy-floyd.out

0 -1 1 -1 -1 
2 0 3 -1 -1 
-1 -1 0 -1 -1 
3 1 4 0 -1 
5 3 5 2 0 

#include <bits/stdc++.h>

using namespace std;

ifstream cin("roy-floyd.in");
ofstream cout("roy-floyd.out");

const int Inf = 0x3f3f3f3f;
int n , m , x , y , w , c[101][101];

void Floyd_Warshall()
{
    for (int k = 1; k <= n; ++k)
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (i != j && c[i][j] > c[i][k] + c[k][j])
                    c[i][j] = c[i][k] + c[k][j];
}

int main()
{
    cin >> n >> m;

    for (int i = 1 ; i <= n ; ++i)
        for (int j = 1 ; j <= n ; ++j)
            if (i != j) c[i][j] = Inf;

    for(int i = 1 ; i <= m ; i++)
    {
        cin >> x >> y >> w;
        c[x][y] = w;
    }

    Floyd_Warshall();

    for (int i = 1 ; i <= n ; ++i)
    {
       for (int j = 1 ; j <= n ; ++j)
            if(c[i][j] != Inf)cout << c[i][j] << ' ';
            else cout << "-1 ";
        cout << '\n';
    }
}