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

using namespace std;

int velikostMatrike = 0;
int C[15][15];

struct Pot{
    vector <int> vozlisca;
    int dolzina;
};

queue<Pot> Q;

void Beri(int G[15][15], string file) {
    fstream dat(file.c_str(), fstream::in);
    dat >> velikostMatrike;
    int p, q, c;

    for(int i=0;i<velikostMatrike;i++){
        for(int j=0;j<velikostMatrike;j++){
            C[i][j]=9999;
        }
    }
    while (!dat.eof()) {
        dat >> p >> q >> c;
        G[p - 1][q - 1] = c;
        C[q - 1][p - 1] = c;
    }
    dat.close();
}

void VstaviVvrsto(queue<Pot> &Q, Pot pot){
    Q.push(pot);
}

Pot VzemiIzVrste(queue<Pot> &Q){
    Pot pot = Q.front();
    Q.pop();
    return pot;
}

Pot DodajVozlisce(Pot &pot, int v)
{
    pot.vozlisca.push_back(v);
    return pot;
}

bool Eksistira(int element, vector<int>vozlisca)
{
    for(unsigned int index=0; index<vozlisca.size(); index++)
        if(element == vozlisca[index])
            return true;
    return false;
}

void VstaviNovoResitev(queue<Pot> &pot, Pot p1){
    for(int index = 0; index < pot.size(); index++)
        pot.pop();
    pot.push(p1);
}

void DodajResitev(queue<Pot> &pot, Pot p1){
    pot.push(p1);
}

void Izpis(queue<Pot> R, int cenaResitve){
    for(int i = 0; i < R.size(); i++){
        cout << R.front().vozlisca[0] << endl;
        cout << R.front().vozlisca[1] << endl;
        cout << R.front().dolzina << endl;
    }
    cout << "R: " << R.front().vozlisca[0] << " in " << R.front().vozlisca[1] << " cena: " << cenaResitve << endl;
}

void RazvejiInOmeji(int G[15][15], int s, int g, queue<Pot> &R, int &cenaResitve){
    Pot pot;
    pot.vozlisca.push_back(s);
    pot.dolzina = 0;
    cenaResitve = 9999;

    VstaviVvrsto(Q, pot);

    while(!Q.empty()){
        Pot p = VzemiIzVrste(Q);
        int u = p.vozlisca.back();
        for(int v = 0; v < velikostMatrike; v++){
            if(!Eksistira(v, p.vozlisca)){
                Pot p1 = DodajVozlisce(p, v);
                p1.dolzina = p.dolzina + C[u][v];
                if(v == g){
                    if(p1.dolzina < cenaResitve){
                        cenaResitve = p1.dolzina;
                        VstaviNovoResitev(R, p1);
                    }
                    else if(p1.dolzina == cenaResitve){
                        cenaResitve = p1.dolzina;
                        DodajResitev(R, p1);
                    }
                }
                else if(p.dolzina < cenaResitve){
                        cenaResitve = p1.dolzina;
                    VstaviVvrsto(Q, p1);
                }
            }
        }
    }
}

int main(){
    int G[15][15];
    queue<Pot> R;
    int s, g, cenaResitve = 0;

    //RazvejiInOmeji(G, s, g, R, cenaResitve);
    int izbira = 0;
    do{
        cout << "Razveji in omeji - izbira" << endl;
        cout << "1 Preberi podatke iz datoteke" << endl;
        cout << "2 Iskanje poti med vozliscema s in q" << endl;
        cout << "3 Konec" << endl;
        cout << "\r\nVasa izbira: ";
        cin >> izbira;
        switch(izbira){
        case 1: Beri(G, "graf.txt"); break;
        case 2: {
                    cout << "Vpisi s: ";
                    cin >> s;
                    cout << "Vpisi g: ";
                    cin >> g;
                    if(s <= 0 || g <= 0 || s > velikostMatrike || g > velikostMatrike)
                        cout << "Neveljaven vnos!" << endl;
                    else{
                        RazvejiInOmeji(G, s, g, R, cenaResitve);
                        Izpis(R, cenaResitve);
                    }

                }break;
        case 3: break;
        default: break;
        }
    }
    while(izbira != 3);
    return 0;
}