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


typedef struct aresta {
    int viz;     // vizinho
    double peso;// peso da aresta
} aresta;

typedef struct vertice {
    int grau;
    list<aresta> AdjL;

    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
// ---------------------------------------
int wdigraph_create(wdigraph& G, string arquivo);
void wdigraph_delete(wdigraph& G);


// -------------------------------------------------------------
// --- MAIN ----------------------------------------------------
// -------------------------------------------------------------
int main() {
    wdigraph G;

    cout<<"\n---------------------------------------------";
    cout<<"\n---------------- DIJKSTRA -------------------";
    cout<<"\n---------------------------------------------\n";
    if (!wdigraph_create(G,"entrada_dijkstra_adjL.txt")) {cout<<"Arquivo inexistente\n"; return -1;}

    dijkstra(G,0);
    wdigraph_delete(G);


    cout<<"\n---------------------------------------------";
    cout<<"\n------------------ PRIM ---------------------";
    cout<<"\n---------------------------------------------\n";
    if (!wdigraph_create(G,"entrada_prim_adjL.txt")) {cout<<"Arquivo inexistente\n"; return -1;}
    prim(G);
    wdigraph_delete(G);

    return 0;
}

// -------------------------------------------------------------
// ---- ALGORITMO DE DIJKSTRA ----------------------------------
// -------------------------------------------------------------
void dijkstra(wdigraph& G, int s) {
    list<aresta>::iterator it;
    if (G.N<=0) return;
    for (int x=0; x<G.N; x++) {
        G.V[x].custo = DBL_MAX;
        G.V[x].pai = s;
        G.V[x].ok = false;
    }
    G.V[s].custo = 0;

    for (int j=1; j<=G.N; j++) {
        int u;
        double custo_min = DBL_MAX;
        for (int x=0; x<G.N; x++) {
            if ((!G.V[x].ok)&&(custo_min >= G.V[x].custo)) {
                custo_min = G.V[x].custo;
                u = x;
            }
        }
        G.V[u].ok = true;
        for (it=G.V[u].AdjL.begin(); it!=G.V[u].AdjL.end(); ++it) {
            int v = (*it).viz;
            double peso = (*it).peso;
            if ((!G.V[v].ok) && (G.V[v].custo > peso + G.V[u].custo)) {
                G.V[v].custo = peso + G.V[u].custo;
                G.V[v].pai = u;
            }
        }
    }

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


// -------------------------------------------------------------
// ---- ALGORITMO DE PRIM --------------------------------------
// -------------------------------------------------------------
void prim(wdigraph& G) {
    list<aresta>::iterator it; int s=0;
    if (G.N<=0) return;
    for (int x=0; x<G.N; x++) {
        G.V[x].custo = DBL_MAX;
        G.V[x].pai = s;
        G.V[x].ok = false;
    }
    G.V[s].custo = 0;

    for (int j=1; j<=G.N; j++) {
        int u;
        double custo_min = DBL_MAX;
        for (int x=0; x<G.N; x++) {
            if ((!G.V[x].ok)&&(custo_min >= G.V[x].custo)) {
                custo_min = G.V[x].custo;
                u = x;
            }
        }
        G.V[u].ok = true;
        for (it=G.V[u].AdjL.begin(); it!=G.V[u].AdjL.end(); ++it) {
            int v = (*it).viz;
            double peso = (*it).peso;
            if ((!G.V[v].ok) && (G.V[v].custo > peso)) {
                G.V[v].custo = peso;
                G.V[v].pai = u;
            }
        }
    }

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


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


// ------------------------------------
// ------------------------------------
int wdigraph_create(wdigraph& G, string arquivo) {
    aresta A;
    ifstream arq;
    arq.open(arquivo.c_str());
    if (arq.fail()) return 0;
    arq >> G.N;
    G.M=0; G.V = NULL;
    G.V = new vertice[G.N];

    for (int x=0; x<G.N; x++) {
        int grau;
        arq >> grau;
        G.V[x].grau = grau;
        G.M += grau;
        for (int k=0; k<grau; k++) {
            int viz; double peso;
            arq >> viz >> peso;
            A.viz = viz; A.peso = peso;
            G.V[x].AdjL.push_back(A);
        }
    }
    arq.close();
    return 1;
}
// ------------------------------------
// ------------------------------------
void wdigraph_delete(wdigraph& G) {
    delete[] G.V;
    G.V = NULL;
}