#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <fstream>
#include <algorithm>
using namespace std;

struct ADMATRIX {
    vector < vector<int> > MATRIX;
};

ADMATRIX* readFile(string input_file);
void TSP_BackTracking(ADMATRIX* matrix, vector<bool>& check, int currentPosition, int n, int count, int weight, int& ans, vector<int>& path, vector<int>& ans_path);
void printTSP(string input_file);

// ReadFile function of MINH DUNG
ADMATRIX* readFile(string input_file) {

    // Declare variables
    ADMATRIX* a = new ADMATRIX;
    string readLine, token;

    //Open file to read the data
    ifstream fin(input_file);
    if (fin.fail()) {
        cout << "Cannot open file" << endl;
    }
    else {
        // 1st line: n cities
        getline(fin, readLine);
        int n = stoi(readLine);

        // Initialize the matrix with n vertices
        vector <int> temp;
        for (int i = 0; i < n; i++)
            temp.push_back(0);
        for (int i = 0; i < n; i++)
            a->MATRIX.push_back(temp);

        //Other lines: CityA CityB Distance
        while (getline(fin, readLine)) {
            vector <int> temp2;
            istringstream ss(readLine);
            while (getline(ss, token, ' ')) {
                temp2.push_back(stoi(token));
            }
            // IMPORTANT: because cities are marked from 1 to n
            // e.g. if we read 1 2 10
            // we will save as 0 1 10
            if (temp2[0] <= n && temp2[1] <= n) {
                a->MATRIX[temp2[0] - 1][temp2[1] - 1] = temp2[2];
                a->MATRIX[temp2[1] - 1][temp2[0] - 1] = temp2[2];
            }
        }
    }
    fin.close();
    return a;
}


// By MINH DUNG
bool isHamiltonPath(ADMATRIX* a, int v, vector<bool> visited, vector<int> path) {

    // If all vertices are visited, then Hamilton path exists
    if (path.size() == a->MATRIX.size())
        return true;

    // Check if every edge starting from vertex v leads to a solution or not
    for (int w = 0; w < a->MATRIX.size(); w++) {
        // process only unvisited vertices as Hamiltonian
        // path visits each vertex exactly once
        if (!visited[w] && a->MATRIX[v][w] != 0) {
            visited[w] = true;
            path.push_back(w);
            // check if adding vertex w to the path leads
            // to solution or not
            if (isHamiltonPath(a, w, visited, path)) {
                return true;
            }

            // Backtrack
            visited[w] = false;
            path.pop_back();
        }
    }
    return false;
}

void printHPath(string input_file)
{

    // Read matrix from file
    ADMATRIX* a = readFile(input_file);

    // Add starting node to the path
    vector <int> path;
    path.push_back(0);

    // Mark starting node as visited
    vector <bool> visited;
    for (int i = 0; i < a->MATRIX.size(); i++) {
        visited.push_back(false);
    }

    // Check Hamilton path
    for (int i = 0; i < a->MATRIX.size(); i++) {
        visited[i] = true;
        if (isHamiltonPath(a, i, visited, path)) {
            cout << "YES" << endl;
            return;
        }
        visited[i] = false;
    }
    cout << "NO" << endl;
}


// By BAO HAN
bool isSafe(int v, ADMATRIX* a, int path[], int pos)
{
    // Check if it is a graph between the last vertex in Hamilton cycle and this vertex
    if (a->MATRIX[path[pos - 1]][v] == 0)
        return false;

    // Check if this vertex has already been included
    for (int i = 0; i < pos; i++)
        if (path[i] == v)
            return false;

    return true;
}

// 'pos' is the number of vertices we have added to Hamilton cycle
bool findHamiltonCycle(int n, ADMATRIX* a, int* path, int pos)
{
    // If all vertices are in Hamilton cycle
    // and the last vertex connect to the first, return true, otherwise return false
    if (pos == n)
    {
        if (a->MATRIX[path[pos - 1]][path[0]] != 0)
            return true;
        else
            return false;
    }

    // Try all vertices (except 0-the initial vertex) as a next candidate in Hamilton cycle
    for (int v = 1; v < n; v++)
    {
        // Check if vertex can be add to Hamilton cycle
        if (isSafe(v, a, path, pos))
        {
            path[pos] = v;

            // Recursive to construct rest of the path
            if (findHamiltonCycle(n, a, path, pos + 1) == true)
                return true;

            // If this vertex doesn't lead to any solution, then remove it
            path[pos] = -1;
        }
    }

    // Can't find the path
    return false;
}

bool isHamiltonCycle(ADMATRIX* a)
{
    int n = a->MATRIX.size();

    // 'path' stores the vertices of Hamilton cycle
    int* path = new int[n];
    for (int i = 0; i < n; i++) path[i] = -1;

    // Initialize by the vertex 0
    path[0] = 0;

    // Find Hamilton cycle
    if (findHamiltonCycle(n, a, path, 1) == false)
        return false;
    else
        return true;
}

void printHCycle(string input_file)
{
    // Read matrix from file
    ADMATRIX* a = readFile(input_file);

    if (isHamiltonCycle(a)) cout << "YES\n"; else cout << "NO\n";
}


// By KY LUONG
// Using BackTracking to find the minimun weight of Hamiltonian Cycle
void TSP_BackTracking(ADMATRIX* matrix, vector<bool>& check, int currentPosition, int n, int count, int weight, int& ans, vector<int>& path, vector<int>& ans_path)
{

    // BASE CASE:
    // If we have traversed all the node of the graph. Keep the minimum weight and the path
    // Finally return to check for more possible values
    if (count == n && matrix->MATRIX[currentPosition][0]) {
        if (ans > weight + matrix->MATRIX[currentPosition][0])
        {
            ans_path = path;
        }
        ans = min(ans, weight + matrix->MATRIX[currentPosition][0]);
        return;
    }

    // BACKTRACKING STEP:
    // Loop to traverse the adjacency list of currentPosition node and increasing the count by 1 and cost by graph[currentPosition][i] value
    for (int i = 0; i < n; i++) {
        if (!check[i] && matrix->MATRIX[currentPosition][i]) {
            // Mark as visited
            check[i] = true;

            // Record the path

            path.push_back(i + 1);

            //Rescursive Call
            TSP_BackTracking(matrix, check, i, n, count + 1, weight + matrix->MATRIX[currentPosition][i], ans, path, ans_path);

            // Mark the node in position i as unvisited
            check[i] = false;
        }
    }
}

void printTSP(string input_file)
{
    ADMATRIX* matrix = readFile(input_file);
    int n = matrix->MATRIX.size();
    vector <bool> check(n);
    for (int i = 0; i < n; ++i)
    {
        check[i] = false;
    }
    check[0] = true;
    int ans = INT_MAX;
    vector<int> path;       // vector that is used to record the path
    vector<int> ans_path;   // vector that is the answer path
    TSP_BackTracking(matrix, check, 0, n, 1, 0, ans, path, ans_path);
    if (ans == INT_MAX)  // ans is still INT_MAX and not change . Therefore, there is no TSP
    {
        cout << "-1" << endl;
    }
    else
    {
        // We realise that the ans_path in some cases is not the path that we are looking for
        // The reason is we have recorded some path in backtracking
        // for example:  ans_path is: 2 3 4 5 5 4 4 3 5 5 3 5 3 4 4 3
        //  Then, the real answer is: 1 2 5 4 3
        // We have to traverse from the end to the beginning of the ans_path and Add at the beginning of the
        // new list if that element is not in the new list yet. Then, add 1 at the beginning.
        //                             (2) 3 4 5 5 4 4 3 5 5 3 (5) 3 4 (4) (3)
        //                            => 1 2 5 4 3

        vector<int> new_list;
        for (int i = ans_path.size() - 1; i >= 0; --i)
        {
            if (find(new_list.begin(), new_list.end(), ans_path[i]) == new_list.end())
            {
                new_list.insert(new_list.begin(), ans_path[i]);
            }
        }
        new_list.insert(new_list.begin(), 1);
        for (int i = 0; i < new_list.size(); ++i)
        {
            cout << new_list[i] << " ";
        }
        cout << endl;
        cout << ans << endl;
    }
    delete matrix;
}


// By NHAT QUANG
void output_main(string action, string input_file)
{
    if (action == "-HPath")
    {
        printHPath(input_file);
    }
    else if (action == "-HCycle")
    {
        printHCycle(input_file);
    }
    else if (action == "-TSP")
    {
        printTSP(input_file);
    }
    else cout << "Error func" << endl;
}

int main(int argc, char* argv[]) {
    string action, input_file;
    if (argc > 2) {
        action = argv[1];
        input_file = argv[2];
        output_main(action, input_file);
    }
    else {
        cout << "Enter action: "; cin >> action;
        cout << "Enter input_file: "; cin >> input_file;
        output_main(action, input_file);
    }
    if (!system(NULL)) system("pause"); return 0;
}