#include <iostream>
#define NUMAR_MAXIM_FILIALE 7
using namespace std;

// stiva folosita pentru backtracking
int stiva[NUMAR_MAXIM_FILIALE];

// date de intrare
int numar_legaturi, numar_filiale, filiala_cautata;

// matrice de adiacenta pentru reprezentarea datelor de intrare sub forma de graf
int legatura[NUMAR_MAXIM_FILIALE + 1][NUMAR_MAXIM_FILIALE + 1];

// tablou in care se retine drumul de cost minim
int ruta_cost_minim[NUMAR_MAXIM_FILIALE], cost_minim = -1;

// tablou folosit pentru parcurgerea functiei exista_drum_intoarcere
bool vizitat[NUMAR_MAXIM_FILIALE + 1];

bool valid(int);
bool solutie(int);
void backtracking(int);
void retine_solutie();
void reseteaza_vizitat();
void exista_drum_intoarcere(int);


int main()
{
    cout << "Introduceti numarul de filiale: ";
    cin >> numar_filiale;
    cout << "Introduceti numarul de legaturi directe dintre filiale: ";
    cin >> numar_legaturi;
    cout << "Introduceti legaturile directe si costurile atasate:\n";
    for(int i = 0; i < numar_legaturi; i++) {
        int filiala1, filiala2, cost;
        cin >> filiala1 >> filiala2 >> cost;
        legatura[filiala1][filiala2] = cost; //legaturile sunt presupuse a fi unidirectionale
    }

    cout << "Introduceti filiala de la care pleaca datele: ";
    int filiala_start;
    cin  >> filiala_start;
    stiva[0] = filiala_start;
    backtracking(1);

    // afisare
    cout << "Costul minim este " << cost_minim << endl;
    cout << "Ruta de cost minim cu drum de intoarcere este: ";
    for(int i = 0; i < numar_filiale; i++) {
        cout << ruta_cost_minim[i] << " ";
    }
    cout << endl;
}

bool valid(int k)
{
    // se verifica existenta unei legaturi intre ultima filiala generata si filiala curenta
    if(!legatura[stiva[k-1]][stiva[k]])
        return 0;

    int cost_curent = 0;
    // se verifica ca filiala sa nu fi fost vizitata precedent
    for(int i = 0; i < k; i++) {
        if(stiva[i] == stiva[k])
            return false;
        cost_curent += legatura[stiva[i]][stiva[i + 1]];
    }

    // costul curent nu trebuie sa depaseasca minimul
    if(cost_minim != -1 && cost_curent >= cost_minim)
        return false;

    return true;
}

void reseteaza_vizitat()
{
    for(int i = 0; i < NUMAR_MAXIM_FILIALE; i++)
        vizitat[i] = false;
}

bool solutie(int k)
{
    reseteaza_vizitat();
    exista_drum_intoarcere(stiva[k]);
    if(k == numar_filiale - 1 && vizitat[stiva[0]])
        return true;
    return false;
}

void retine_solutie()
{
    cost_minim = 0;
    for(int i = 0 ; i < numar_filiale; i++) {
        cost_minim += legatura[i][i + 1];
        ruta_cost_minim[i] = stiva[i];
    }
}

void backtracking(int k)
{
    // se presupune ca numerotarea filialelor incepe de la 1
    for(int i = 1; i <= numar_filiale; i++) {
        stiva[k] = i;
        if(valid(k)) {
            if(solutie(k))
                retine_solutie();
            else {
                backtracking(k+1);
                stiva[k] = 0;
            }
        }
    }
}

void exista_drum_intoarcere(int filiala_curenta)
{
    vizitat[filiala_curenta] = true;

    for(int i = 1; i <= numar_filiale; i++) {
        if(legatura[filiala_curenta][i] && !vizitat[i]) {
            exista_drum_intoarcere(i);
        }
    }
}