FloydWarshall

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

#define INF 1e9

int D[600][600]; ///Matriz de adyacencia
int N; ///La cantidad de nodos

void floydWarshall()
{
    ///Para cada par de nodos i, j
    ///Qué es mejor, la distancia que tengo calculada
    ///o ir de i->k y luego de k->j ?

    for(int k=1; k<=N; k++)
        for(int i=1; i<=N; i++)
            for(int j=1; j<=N; j++)
                D[i][j] = min(D[i][j], D[i][k]+D[k][j]);
}

int main()
{
    int cantAristas;
    int a, b, c;
    cin >> N >> cantAristas;

    ///Llenar inicialmente todas las distancias con infinito
    ///En D[i][i] decidimos que la distancia es cero
    ///(o sea, para llegar de i hasta i, no te movés, cero distancia)

    for(int i=1; i<=N; i++)
        for(int j=1; j<=N; j++)
            D[i][j] = INF;

    for(int i=1; i<=N; i++)
        D[i][i] = 0;

    for(int i=0; i<cantAristas; i++)
    {
        cin >> a >> b >> c;
        D[a][b] = c;
        D[b][a] = c;
    }

    /**
    Floyd Warshall es un algoritmo que calcula
    la distancia entre cada par de nodos
    en tiempo O(N^3), lo que no es rápido, pero
    que en algunas circunstancias es suficiente
    **/

    floydWarshall();

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

    return 0;
}

/**
Ejemplo de input:
6 9
1 2 7
1 3 9
1 6 14
2 3 10
2 4 15
3 4 11
3 6 2
4 5 6
5 6 9

Output correcto:
0 7 9 20 20 11
7 0 10 15 21 12
9 10 0 11 11 2
20 15 11 0 6 13
20 21 11 6 0 9
11 12 2 13 9 0
**/