#include <iostream>
#include <stack>
#include <list>
#include <algorithm>

using namespace std;

     
class Route
{
    private:
        int _count;
        long _length;
        list<int> _cities;     
        void add_distance(int* cityA, int* cityB);        
    public:    
        Route() { _count = 0; _length = 0; };
        Route(int start) { _cities.push_back(start); Route::Route();};
        int count() { return _count; };
        long length(){ return _length; };
        bool empty() { return _cities.empty(); };
        void display ();
        bool visited (int city);
        void visit (int city);
};

void Route::add_distance(int* cityA, int* cityB)
{
    if (*cityA == *cityB)
        return;
    int n = *cityA + 1, m = *cityB + 1;
    _length += (n*m + n*m/4)%(97) + n + m;
    return;
}

void Route::display()
{
    list<int>::iterator i=_cities.begin();
    cout << "displaying route:" << endl;
    while(i != _cities.end())
    {        
        cout << " -> " << *i;
        i++;
    }
    cout << endl << count() << " cities visited." << endl;
    cout << "Length of this route: " << _length << endl; 
    return;
}

bool Route::visited (int city)
{
    if (find(_cities.begin(), _cities.end(), city) == _cities.end())
        return false;
    else
        return true;
}

void Route::visit (int city)
{
    int last_city = _cities.back();    
    _count++;

    if (empty() == false)
        add_distance(&last_city, &city);

    _cities.push_back(city);
    return;
}        

class Salesman
{
    private:
        stack<Route> _routes;
        int _cities;
        Route _shortest;
        void find_algorithm();
    public:
        //salesman();
        void find_shortest_route() {find_algorithm(); };
        void set_cities (int cities) { _cities = cities; };
        void display_shortest_route() {_shortest.display(); };
};
  
void Salesman::find_algorithm ()
{    
    for (int i=0; i < _cities; i++)
    {
        _shortest.visit(i);
    }
    Route init_route;
    init_route.visit(0);
    _routes.push(init_route);    
    
    while ( _routes.empty() == false)
    {        
        if (_routes.top().count() >= _cities)
        {
            _routes.top().visit(0);
            
            if (_routes.top().length() < _shortest.length())
                _shortest = _routes.top();            
                
            _routes.pop();
        }
        else
        {
            Route tr1, tr2;
            tr1 = _routes.top();
            _routes.pop();            
            for (int j=1; j < _cities; j++)
            {
                if (tr1.visited(j) == false)
                {                    
                    tr2 = tr1;
                    tr2.visit(j);
                    if (tr2.length() < _shortest.length())
                        _routes.push(tr2);                  
                }
            }
        }        
    }
    return;
}
     
        


int main()
{    
    Salesman problem;
    
    problem.set_cities(11);
    system("PAUSE");
    
    problem.find_shortest_route();
    
    problem.display_shortest_route();

    system("PAUSE");
    return 0;
}