#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>

using namespace std;

class Graph{

    //DATE MEMBRE
private:

    int m_graph_nodes;
    //numar de noduri

    vector<vector<int>> m_graph_adjacency_list;
    //lista de adiacenta

    vector<vector<pair<int,int>>> m_graph_adjacency_list_with_costs;
    //lista de adiacenta pentru graf cu costuri

    vector<vector<int>> m_costs_matrix;
    //matricea de costuri pentru grafuri ponderate

    vector<vector<int>> m_capacities;


public:
    //METODELE CLASEI

    //CITIRILE

    void read_graph_with_costs_as_costs_matrix(char *file);
    //citire graf orientat ponderat cu matricea costurilor

    void read_transport_routes(char *file);
    //citire retea de trasnport

    //ALGORITMI FUNDAMENTALI

    vector<vector<int>> roy_floyd();
    //algoritmul roy floyd -> returneaza matricea drumurilor din matricea costurilor asociata grafului apelant

    //HELPERE
    void print_path_matrix(vector<vector<int>> path_matrix, char *file);
    //functia care afiseaza in fisier matricea drumurilor
};

//METODELE PUBLICE

//  CITIRI

void Graph::read_graph_with_costs_as_costs_matrix(char *file) {
    ifstream f(file);
    vector<int> aux;

    f >> this->m_graph_nodes;

    m_costs_matrix.push_back(aux);

    for(int i = 1; i <= this->m_graph_nodes; i++){
        vector<int> linie;
        linie.push_back(0);

        for(int j = 1; j <= this->m_graph_nodes; j++){
            int val;
            f >> val;
            linie.push_back(val);
        }

        m_costs_matrix.push_back(linie);
    }
}

void Graph::read_transport_routes(char *file) {
    ifstream f(file);
    int number_edges;
    vector<int> aux;

    f >> this->m_graph_nodes;
    this->m_graph_adjacency_list.assign(this->m_graph_nodes + 1, aux);

    aux.assign(this->m_graph_nodes + 1, 0);
    this->m_capacities.assign(this->m_graph_nodes + 1, aux);

    f >> number_edges;

    for(int i = 0; i < number_edges; i++){
        int x, y, z;

        f >> x >> y >> z;

        this->m_capacities[x][y] = this->m_capacities[x][y] + z;

        this->m_graph_adjacency_list[x].push_back(y);
        this->m_graph_adjacency_list[y].push_back(x);
    }
}

//ALGORITMI FUNDAMENTALI

vector<vector<int>> Graph::roy_floyd() {
    vector<vector<int>> path_matrix;
    vector<int> aux;

    aux.assign(this->m_graph_nodes + 1, 0);
    path_matrix.assign(this->m_graph_nodes + 1, aux);

    for(int i = 1; i <= this->m_graph_nodes; i++){

        for(int j = 1; j <= this->m_graph_nodes; j++){

            path_matrix[i][j] = this->m_costs_matrix[i][j];
        }
    }

    for(int k = 1; k <= this->m_graph_nodes; k++){

        for(int i = 1; i <= this->m_graph_nodes; i++){

            for(int j = 1; j <= this->m_graph_nodes; j++){

                    if(i != j && path_matrix[i][k] != 0 && path_matrix[k][j] != 0){

                        if(path_matrix[i][j] > path_matrix[i][k] + path_matrix[k][j]){

                            path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];

                        }else if (path_matrix[i][j] == 0){

                            path_matrix[i][j] = path_matrix[i][k] + path_matrix[k][j];
                        }
                    }
            }
        }
    }

    return path_matrix;
}

//HELPERE

void Graph::print_path_matrix(vector<vector<int>> path_matrix, char *file) {

    ofstream out(file);

    for(int i = 1; i <= this->m_graph_nodes; i++){

        for(int j = 1; j <= this->m_graph_nodes; j++){
            out<<path_matrix[i][j]<<" ";
        }

        out<<"\n";
    }
}

int main() {

    //FLOYD WARSALL INFOARENA

    /*Graph g;
    g.read_graph_with_costs_as_costs_matrix("../royfloyd.in");

    vector<vector<int>> path_matrix;
    path_matrix = g.roy_floyd();
    g.print_path_matrix(path_matrix,"../royfloyd.out");*/

    //MAXFLOW INFOARENA

    Graph g;
    g.read_transport_routes("../maxflow.in");
    return 0;
}