// ------------------------------------------------------------
// ---- ALGORITMOS DE DIJKSTRA E PRIM --------------------------
// -------------------------------------------------------------
#include <iostream>
#include <fstream>
#include <cmath>
#include <ctime>
#include <climits>
#include <cfloat>
#include <windows.h>
#include <stack>
using namespace std;


typedef struct vertice {
    int grau;
    int* adjL;
    double* adjW;

    double custo;
    int pai;
    bool ok;
} vertice;

typedef struct wdigraph {
	int N;// numero de vertices
	int M;// numero de arestas
	vertice* V;
} wdigraph;


// ---------------------------------------
// Algoritmos de DIJKSTRA e PRIM
// ---------------------------------------
void dijkstra(wdigraph& G, int s);
void prim(wdigraph& G);


// ---------------------------------------
// Manutenção de grafos
// ---------------------------------------
void wdigraph_create(wdigraph& G, string arquivo);
void wdigraph_delete(wdigraph& G);


// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
    int i,j,k;

    wdigraph G;

    cout<<"---------------------------------------------"<<endl;
    cout<<"---------------- DIJKSTRA -------------------"<<endl;
    cout<<"---------------------------------------------"<<endl;
    wdigraph_create(G,"entrada_dijkstra_adjL.txt");
    dijkstra(G,0);
    wdigraph_delete(G);
    cout<<endl;

    cout<<"---------------------------------------------"<<endl;
    cout<<"------------------ PRIM ---------------------"<<endl;
    cout<<"---------------------------------------------"<<endl;
    wdigraph_create(G,"entrada_prim_adjL.txt");
    prim(G);
    wdigraph_delete(G);
    cout<<endl;

    return 0;
}

// -------------------------------------------------------------
// ---- ALGORITMO DE DIJKSTRA ----------------------------------
// -------------------------------------------------------------
void dijkstra(wdigraph& G, int s) {
    if (G.N<=0) return;
    int i,j,k;
    for (i=0; i<G.N; i++) {
        G.V[i].custo = DBL_MAX;
        G.V[i].pai = s;
        G.V[i].ok = false;
    }
    G.V[s].custo = 0;

    for (j=0; j<G.N; j++) {
        int u;
        double dist_min = DBL_MAX;
        for (i=0; i<G.N; i++) {
            if ((!G.V[i].ok)&&(dist_min >= G.V[i].custo)) {
                dist_min = G.V[i].custo;
                u = i;
            }
        }
        G.V[u].ok = true;
        for (k=0; k<G.V[u].grau; k++) {
            int v = G.V[u].adjL[k];
            if ((!G.V[v].ok) && (G.V[v].custo > G.V[u].custo + G.V[u].adjW[k])) {
                G.V[v].custo = G.V[u].custo + G.V[u].adjW[k];
                G.V[v].pai = u;
            }
        }
    }

    for (i=0; i<G.N; i++) {
        cout<<"dist["<<s<<"]["<<i<<"]="<<G.V[i].custo<<" / pai="<<G.V[i].pai<<endl;
    }
}


// -------------------------------------------------------------
// ---- ALGORITMO DE PRIM --------------------------------------
// -------------------------------------------------------------
void prim(wdigraph& G) {
    if (G.N<=0) return;
    int i,j,k;
    int s = 0;
    for (i=0; i<G.N; i++) {
        G.V[i].custo = DBL_MAX;
        G.V[i].pai = s;
        G.V[i].ok = false;
    }
    G.V[s].custo = 0;
    for (j=0; j<G.N; j++) {
        int u = -1;
        double custo_min = DBL_MAX;
        for (i=0; i<G.N; i++) {
            if ((!G.V[i].ok)&&(custo_min >= G.V[i].custo)) {
                custo_min = G.V[i].custo;
                u = i;
            }
        }
        G.V[u].ok = true;
        for (k=0; k<G.V[u].grau; k++) {
            int v = G.V[u].adjL[k];
            if ((!G.V[v].ok) && (G.V[v].custo > G.V[u].adjW[k])) {
                G.V[v].custo = G.V[u].adjW[k];
                G.V[v].pai = u;
            }
        }
    }

    double custo_total = 0;
    for (i=0; i<G.N; i++) {
        custo_total += G.V[i].custo;
        cout<<"pai["<<i<<"]="<<G.V[i].pai<<endl;
    }
    cout<<"Custo total = "<<custo_total<<endl;
}


// -------------------------------------------------------------
// ---- MANUTENÇÃO DE GRAFOS -----------------------------------
// -------------------------------------------------------------


// ------------------------------------
// ------------------------------------
void wdigraph_create(wdigraph& G, string arquivo) {
    G.N=0; G.M=0;
    G.V = NULL;

    ifstream arq;
    arq.open(arquivo.c_str());
    if (arq.fail()) return;

    arq >> G.N;
    G.V = new vertice[G.N];
    for (int i=0; i<G.N; i++) {
        int grau;
        arq >> grau;
        G.V[i].grau = grau;
        G.M += grau;
        G.V[i].adjL = new int[grau];
        G.V[i].adjW = new double[grau];
        for (int k=0; k<grau; k++) {
            arq >> G.V[i].adjL[k];
            arq >> G.V[i].adjW[k];
        }
    }
}

// ------------------------------------
// ------------------------------------
void wdigraph_delete(wdigraph& G) {
    for (int i=0; i<G.N; i++) {
        if (G.V[i].adjL != NULL) delete[] G.V[i].adjL;
        if (G.V[i].adjW != NULL) delete[] G.V[i].adjW;
        G.V[i].adjL = NULL;
        G.V[i].adjW = NULL;
    }
    delete[] G.V;
    G.V = NULL;
}