Create a new version of paste:

#include <iostream>
#include <vector>
#include <time.h>
#include <utility>
#include <stdlib.h>
#include <list>
#include <string.h>
#include <map>
#include <limits.h>


#define LIMIT_CONSTRUCTION_VALUE 2100 //limite que poda a matriz de adjacencia
#define LIMIT_NEIGHBORHOOD_FAILURE 5 // limite de falhas na melhoria externa da movimentação de vizinhança
#define INITIAL_MATRIX_CEIL_VALUE 999999 //valores randomicos da matriz vão ser gerados de 1 até este valor
#define GRASP_MAX_ITER 50 // numero de iterações do grasp
#define GRASP_ALPHA_VALUE 0.5 //porcentagem de aleatoriedade do grasp

using namespace std;

typedef vector<vector<int> > vv;
typedef vector<list<pair<int, int> > > vlp; // <node, cost>

//Auxiliar functions:
void print_matrix(vv);
void print_list(vlp);
void print_global_solution(pair<int, vector<int> >);
void print_vec(vector<int> vec);
bool not_in(int, vector<int>);

//algorithm functions:
void fill_matrix(vv &adj, int size){ // preenche a matrix com valores aleatórios, grafo completo e undirected

	srand(time(NULL));
	vector<int> aux(size);
	adj.reserve(size);

	for (int i = 0; i<size; i++) {

		for (int j = i; j<size; j++)
			if (i == j)
				aux[j] = 0;
			else
				aux[j] = rand() % INITIAL_MATRIX_CEIL_VALUE + 1; // valores entre 1 e 50

		adj.push_back(aux);
	}

	for (int i = 0; i < size; i++) {  //espelha o triangulo superior (grafo undirected)
		for (int j = 0; j < size; j++) {
			adj[j][i] = adj[i][j];
		}
	}
}

std::vector< std::vector<int> > readInput()
{
    int route = 0, 
        numberInput = 0;

    std::cin >> route;

    std::vector< std::vector<int> > mDistance;

  for (int i = 0; i < route; i++)
  {
      std::vector<int> vTemp;
      for (int j = 0; j < route; j++)
      {
           std::cin >>  numberInput;
           vTemp.push_back ( numberInput ); 
      }
      mDistance.push_back( vTemp );
  }

 std::cout << "\n \t *************** \n" << std::endl;
  // Print out the elements
   for(unsigned int i = 0; i< mDistance.size(); i++) 
   {
      for (unsigned int j = 0; j < mDistance[i].size(); j++)
          std::cout << "\t" <<  mDistance[i][j] << " "; 

      std::cout << std::endl;
   }

   return mDistance;

}

vlp construction(vv &adj, int limit){ // converte a matriz numa lista, setando valores de distancia acima do parametro como intratáveis
	int size = adj.size();
	vlp adj_list(size);

	for(int i=0; i<size; i++)
		for(int j=0; j<size; j++)
			if(i!=j)
				if(adj[i][j] <= limit)
					adj_list[i].push_back(make_pair(j, adj[i][j]));


	return adj_list;
}

vector<int> grasp_solution(vlp adj, int P, float alpha){

    multimap<float, int> medias;
    vector<int> random_set;
    vector<int> solution;
    float media, alpha_part;
    int size_list = adj.size(), total_part, random, cont=0, random_set_size;

    print_list(adj);

    for(int i=0; i<size_list; i++){
        media = 0;
        for(list<pair<int, int> >::iterator it = adj[i].begin(); it!=adj[i].end(); it++){
            media += it->second;
        }
        media /= adj[i].size();
        medias.insert(make_pair(media, i));
    }

    cout << "Medias ordenadas (media, nó): " << endl;
    for(multimap<float, int>::iterator it = medias.begin(); it!=medias.end(); it++){
        cout << "( " << it->first << " , " << it->second << " )" << endl;
    }

    alpha_part = P * alpha;
    total_part = P + alpha_part;
    cout << "P: " << P << endl;
    cout << "alpha part: " << alpha_part << endl;
    cout << "total part: " << total_part << endl;

    for(int i=0; i<P; i++){
        random_set_size = random_set.size();
        do{
            random = rand() % (total_part+1);
            if(not_in(random, random_set)){
                cout << "random: " << random << endl;
                random_set.push_back(random);
            }
        }while(random_set_size==random_set.size());
    }

    multimap<float, int>::iterator map_iter = medias.begin();

    for(int i=0; i<P; i++){
        map_iter = medias.begin();
        for(int j=0; j<random_set[i]; j++)
            map_iter++;
        solution.push_back(map_iter->second);
    }

    cout << "solucao:" << endl;
    print_vec(solution);

    return solution;
}

// soma local com LISTA
int local_sum(vlp adj, vector<int> solution){
	int size_list = adj.size(), size_sol = solution.size(), min, sum=0;
	bool pass;

	for(int i=0; i<size_list; i++){

		min = INT_MAX;
		pass = true;
		for(int g=0; g<size_sol; g++)
			if(i==solution[g])
				pass = false;

		if(pass){
			for(list<pair<int, int> >::iterator it = adj[i].begin(); it != adj[i].end(); it++)
				for(int g=0; g<size_sol; g++)
					if(it->first == solution[g])
						if(it->second < min)
							min = it->second;


			if(min != INT_MAX){
				sum += min; // soma os mínimos para cada nó
			}
		}
	}
	return sum; // retorna a soma
}

vector<int> random_permutation(vlp adj_list, vector<int> partial_solution){

	int adj_size = adj_list.size(), partial_size = partial_solution.size(), random[2];

	random[0] = rand() % partial_size;

	do{
		random[1] = rand() % adj_size;
	}while(!not_in(random[1], partial_solution));

	partial_solution[random[0]] = random[1];

	return partial_solution;
}

pair<int, vector<int> > neighborhood_moviments(vlp adj_list, vector<int> initial_solution){ // essa função vai fazer as permutações e calcular as somas

	int best_local_sum = INT_MAX, init_size = initial_solution.size(), partial_sum, not_improve = 0;
	vector<int> best_local_solution, partial_solution = initial_solution;
	bool improve=true;

	best_local_sum = local_sum(adj_list, partial_solution); // solução inicial
	best_local_solution = partial_solution;
	cout << "initial sum: " << best_local_sum << endl;
	cout << "initial solution: ";
	print_vec(best_local_solution);
	cout << endl;

	while(improve){

		initial_solution = partial_solution;

		if(not_improve>=LIMIT_NEIGHBORHOOD_FAILURE){
			cout << "not_improve >= " << LIMIT_NEIGHBORHOOD_FAILURE << "... interrompendo movimentação" << endl;
			break;
		}

		improve = false;

		for(int i=0; i<init_size; i++){
			for(list<pair<int, int> >::iterator it = adj_list[initial_solution[i]].begin(); it != adj_list[initial_solution[i]].end(); it++){


				if(not_in(it->first, partial_solution)){
					cout << "antes da troca: ";
					print_vec(partial_solution);
					partial_solution[i] = it->first;
				}else
					continue;
				cout << "depois da troca: ";
				print_vec(partial_solution);
				cout << "soma pos troca: ";
				partial_sum = local_sum(adj_list, partial_solution);
				cout << partial_sum;
				cout << endl;

				if(partial_sum<best_local_sum){
					cout << "essa solução foi a melhor até agora" << endl;
					best_local_sum = partial_sum;
					best_local_solution = partial_solution;
					improve = true;
				}

			}

			partial_solution[i] = initial_solution[i];
		}

		cout << "antes da permutação randomica:";
		print_vec(partial_solution);
		partial_solution = random_permutation(adj_list, partial_solution);
		cout << "depois da permutação randomica: ";
		print_vec(partial_solution);

		if(!improve){
			not_improve++;
			cout << "não melhorou... not_improve: " << not_improve << endl;
			improve = true;
		}

	}

	return make_pair(best_local_sum, best_local_solution);
}

int main()
{
	vv adj_matrix = readInput();
	vlp adj_list, original_list, heuristic_list;
	int P, V;
	vector<int> initial_solution;
	pair<int, vector<int> > global_solution, local_solution;
	global_solution.first = INT_MAX;

	/*cout << "Defina tamanho do grafo ( V ):";
	cin >> V;*/

	//fill_matrix(adj_matrix, V);
    original_list = construction(adj_matrix, INITIAL_MATRIX_CEIL_VALUE);
    heuristic_list = construction(adj_matrix, LIMIT_CONSTRUCTION_VALUE);

	do{
		cout << "defina P ( P < V and P > 0):";
		cin >> P;
	}while(P>=V && P<=0);

    for(int i=0; i<GRASP_MAX_ITER; i++){
        //formando clusters (heuristica de construção utilizando um parâmetro que define oque é perto e o que é longe)
        adj_list = heuristic_list; // (matrix, limit_value)

        //seleção gulosa de medianas
        initial_solution = grasp_solution(adj_list, P, GRASP_ALPHA_VALUE);

        //essa linha retorna a lista pra o estado original da matrix
        adj_list = original_list;

        //busca local (retorna a soma das distanticas dos clientes a sua facilidade mais próxima para uma dada seleção de medianas), insere o par <soma, solução> no multimap de soluções locais
        local_solution = neighborhood_moviments(adj_list, initial_solution);

        //fica só com a melhor
        global_solution = local_solution.first<global_solution.first?local_solution:global_solution;
    }
	print_global_solution(global_solution);

    return 0;
}


//implementação de funções auxiliares
void print_matrix(vv adj) {

	int size = adj.size();
	cout << "Matrix:" << endl;

	for (int i = 0; i<size; i++) {
		for (int j = 0; j<size; j++)
			cout << adj[i][j] << " ";

		cout << endl;
	}
}

void print_list(vlp adj_list){

	int len = adj_list.size();
	typename list<pair<int, int> >::iterator it;

	cout << "List(node, cost):" << endl;

	for(int i=0; i<len; i++){

		cout << "[" << i << "] -> ";

		for(it=adj_list[i].begin(); it!=adj_list[i].end(); it++)
				cout << "(" << it->first << " , " << it->second << ") -> ";

		cout << endl;
	}
}

void print_global_solution(pair<int, vector<int> > result){

	int size = result.second.size();
	cout << "Melhor resultado da heuristica: " << endl;
	cout << "( " << result.first << " , [,";
	for(int i=0; i<size; i++)
		cout << result.second[i] << ",";
	cout << "] )" << endl;
}

void print_vec(vector<int> vec){
	int size = vec.size();

	for(int i=0; i<size; i++)
		cout << vec[i] << ",";
	cout << endl;
}

bool not_in(int test, vector<int> vec){
	int size = vec.size();
	for(int i=0; i<size; i++)
		if(test==vec[i])
			return false;
	return true;
}