void LongestCommonSubsequence::printSolution(int begin, int end) const
{
	if (b[begin-1][end-1] == 'd') {
		printSolution(begin - 1, end - 1);
		std::cout << " " << X[begin-1];
	}
	else if (b[begin-1][end-1] == 't') {
		printSolution(begin - 1, end);
	}
	else if (b[begin - 1][end - 1] == 'l') {
		printSolution(begin, end - 1);
	}
}

/* Извежда резултата на екрана */
void printSolution(int x, int y)
{ if (x > 0 && y > 0 && F[x][y].value > 0) {
    if (F[x][y].action > 0) {
      printSolution(F[x][y].action, y);
      printSolution(x - F[x][y].action, y);
    }
    else if (F[x][y].action < 0) {
      printSolution(x, -F[x][y].action);
      printSolution(x, y - (-F[x][y].action));
    }
    else
      printf("(%2u,%2u) --> %2u  ", x, y, F[x][y].value);
  }
}

       bool must_search_for_other_solutions(Node const& p, Robot::names r_)
       {
           if (m_solutions[r_].nrj() == 0) // new solution
           {
               {
                   this->m_stats.printSituationSoFar(true);
                   std::cout << "\nGOAL reached for " << Robot::toString(r_) << " in " << p.nrj() << " moves" << ": " <<std::flush;
                   // print solution
#if 0
                   Node last=p;
                   while (true)
                   {
                       std::cout << "\n <- " << last << std::flush;
                       const Set::iterator wh = this->m_seen.find(last.m_previous);
                       if (wh == this->m_seen.end()) break;
                       std::cout << "[" 
                           << Robot::toString(last.link().robot()) << Directions::toString(last.link().direction())
                           << "]" << std::flush;
                       last = *wh;
                   }
                   std::cout << std::endl;
#endif

                   printSolution(p, this->previous(), Robot::MAX__);
                   std::cout << "\n" << std::endl;
               }

               m_solutions[r_] = p;
               for (Robot::names r=Robot::names(0) ; r!=Robot::MAX__; ++r)
                   if (m_solutions[r].nrj()==0)
                       return true;
               return false;
           }
           return true;
       }

int BreadthFirstSearch::returnSolution(const string & start, const string & end,  string & sol)
{
	int startIndex=AdjacencyMatrix.getNameIndex(start);
	int endIndex=AdjacencyMatrix.getNameIndex(end);
	queue.push(startIndex);
	AdjacencyMatrix.getVertex(startIndex).color=GREY;
	if(BFS(endIndex))
	{
		cout<<"BFS solution found\n";
		printSolution(endIndex,sol);
		sol.erase(sol.end()-1);
	}

	ofstream bfsOutputFile(outputFileName.c_str(),ios::out);
	if (!bfsOutputFile)
	{
		cerr << "Uh oh, " << outputFileName << " could not be opened for writing!" << endl;
		exit(1);
	}
	
	bfsOutputFile<<sol;
	bfsOutputFile.close();


	return 1;
}

void dijkstra(int graph[V][V], int src)
{
    int dist[V];
    
    bool sptSet[V];
    
    for(int i=0; i<V; i++)
        dist[i] = INT_MAX, sptSet[i] = false;
    
    dist[src] = 0;
    
    for(int count =0; count < V-1; count++)
    {
        int u = minDistance(dist, sptSet);
        sptSet[u] = true;
        
        for(int v=0; v<V; v++)
            if(!sptSet[v] && graph[u][v] 
            && dist[u] != INT_MAX 
            && dist[u] + graph[u][v] < dist[v])
                dist[v]  = dist[u] + graph[u][v];
    }
    
    printSolution(dist, V);
}

int DepthFirstSearch::returnSolution(const string & start, const string & end, string & sol)
{
	int startIndex=AdjacencyMatrix.getNameIndex(start);
	int endIndex=AdjacencyMatrix.getNameIndex(end);
	
	if (DFS(startIndex,endIndex))
	{
		cout<<"DFS solution found!\n";
		printSolution(endIndex,sol);
		sol.erase(sol.end()-1);
	}

	ofstream dfsOutputFile(outputFileName.c_str(),ios::out);
	if (!dfsOutputFile)
	{
		cerr << "Uh oh, " << outputFileName << " could not be opened for writing!" << endl;
		exit(1);
	}
	
	dfsOutputFile<<sol;
	dfsOutputFile.close();

	return 1;
	
}

// Main recursive function used to solve the program
int solve(int step, cell_t* myCells, constraint_t* myConstraints,
          long long* myNodeCount) {
  int cellIndex;
  int value = UNASSIGNED_VALUE;

  if (found)
    return 1;

  if (step == totalNumCells) {
    // Print out solution and set found to true
    #pragma omp critical
    {
      if (!found) {
        printSolution(myCells);
        found = 1;
      }
    }

    return 1;
  }

  (*myNodeCount)++;
  // Find the next cell to fill and test all possible values
  if ((cellIndex = getNextCellToFill(myCells, myConstraints)) < 0)
    return 0;

  while (UNASSIGNED_VALUE != (value = applyNextValue(myCells, myConstraints,
                                                     cellIndex, value))) {
    if (solve(step + 1, myCells, myConstraints, myNodeCount))
      return 1;
  }

  return 0;
}

int main(void) { 
  init();
  printf("\nМаксимална цена %u", solve(sizeX, sizeY));
  printf("\nРазмери (X,Y)-->Цена\n");
  printSolution(sizeX, sizeY);
  return 0;
}

void back() {

     int HS;

     init();

     while(level > 0) {

           do{}while((HS=has_next()) && !isValid()); 

           if( HS ) {

             if(solution()) {

                printSolution();

             } else {

                level = level + 1;
                init(); 

             }

           } else {

             level = level - 1;
           }
     }
}

int main(){
	int resultanceMatrix[MAXVERTEX][MAXVERTEX][MAXVERTEX];
	int n, m;
  int origin, master, distance, lookTrip, cityDistance, test = 0;
  
  while(scanf("%d %d", &n, &m) != EOF){
	  if(test >= 1)
      printf("\n");
    test++;

	  initialize(resultanceMatrix, n);

	  for(int i = 0; i < m; i++){
	    scanf("%d %d %d", &origin, &master, &distance);
	    if(resultanceMatrix[0][origin][master] > distance)
	    	resultanceMatrix[0][origin][master] = distance;
	  }

		floydWarshall(resultanceMatrix,n);

		printf("Instancia %d\n", test);
    scanf("%d", &lookTrip);
    for(int i = 0; i < lookTrip;i++){
      scanf(" %d %d %d", &origin, &master, &cityDistance);
      printSolution(resultanceMatrix,origin,master,cityDistance,n);
    }
	}
	return 0;
}

void solveTour(int &sizeX, int &sizeY, int &startX, int &startY)
{
	/* Create an array that will contain the solution */
	// allocate the solution array
	int** solution = new int*[sizeX];
	for (int i = 0; i < sizeX; i++)
		solution[i] = new int[sizeY];

	/* Set all position to -1 */
	for (int x = 0; x < sizeX; x++)
		for (int y = 0; y < sizeY; y++)
			solution[x][y] = -1;

	/* All 8 of the possible move options for the knight */
	int xMove[8] = { 2, 1, -1, -2, -2, -1, 1, 2 };
	int yMove[8] = { 1, 2, 2, 1, -1, -2, -2, -1 };

	/* Knight will start and the square chosen by the user */
	solution[startX][startY] = 0;

	/* Start at current position and from there explore all tours using exploreTours() */
	if (exploreTours(sizeX, sizeY, startX, startY, 1, solution, xMove, yMove) == false)
	{
		printf("No solution found");
	} else {
		printSolution(sizeX, sizeY, solution);
		printf("\n\nsolved!\n");
	}

}

/* This function solves the Knight Tour problem using Backtracking.  This
function mainly uses solveKTUtil() to solve the problem. It returns false if
no complete tour is possible, otherwise return true and prints the tour.
Please note that there may be more than one solutions, this function
prints one of the feasible solutions.  */
bool solveKT()
{
    int sol[N][N];
 
    /* Initialization of solution matrix */
    for (int x = 0; x < N; x++)
        for (int y = 0; y < N; y++)
            sol[x][y] = -1;
 
    /* xMove[] and yMove[] define next move of Knight.
       xMove[] is for next value of x coordinate
       yMove[] is for next value of y coordinate */
    int xMove[8] = {  2, 1, -1, -2, -2, -1,  1,  2 };
    int yMove[8] = {  1, 2,  2,  1, -1, -2, -2, -1 };
 
    // Since the Knight is initially at the first block
    sol[0][0]  = 0;
 
    /* Start from 0,0 and explore all tours using solveKTUtil() */
    if(solveKTUtil(0, 0, 1, sol, xMove, yMove) == false)
    {
        printf("Solution does not exist");
        return false;
    }
    else
        printSolution(sol);
 
    return true;
}

void printPuzzle(Puzzle *puzzle) {
    int i, j, size = puzzle->size;
    printf("\n\nDificulty: %d x %d\n", size, size);
    printf("Shuffles: %d\n\n", shuffleCount);
    
    printBorder(size);
    
    for (i = 0; i < size; i++) {
        printf("%5c#|", ' ');
        for (j = 0; j < size; j++) {
            if(puzzle->matrix[i][j] == 0) {
                if(puzzle->inverted)
                    printf("%2c", ' ');
                else
                    printf("%2d", 0);
            } else {
                printf("%2d", puzzle->matrix[i][j]);
            }
            printf("|");
        }
        printf("#\n");
    }
    
    printBorder(size);
    printMenu();
    
    if(showSolution && puzzle->solution->size > 0)
        printSolution(puzzle->solution);
}

void santaVisit(int current, int depth)
{
	candidate[depth] = current;

	if (depth == 8)
	{
		printSolution();
		return;
	}

	for (int i = 1; i <= 5; i++)
	{
		// if connected and not visited yet
		if (house[current][i] && !edgeVisited[current][i])
		{
			edgeVisited[current][i] = true; // mark this edge visited
			edgeVisited[i][current] = true; // mark this edge visited, bidirectional 

			santaVisit(i, depth + 1);

			// backtrack
			edgeVisited[current][i] = false; // undo this edge visited
			edgeVisited[i][current] = false; // undo this edge visited, bidirectional 
		}
	}
}

int main(int argc, char *argv[]){

	int start, goal, d, nodeCount = 0;
	
	if (argc < 3) {
		fprintf(stderr, "Usage: %s start goal [-verbose/-v]\n", argv[0]);
		return EXIT_FAILURE;
	}

	if (argc == 4 && (strcmp(argv[3], "-v") == 0 || strcmp(argv[3], "-verbose") == 0)){
		verbose = 1;
	}

	start = atoi(argv[1]);
	goal = atoi(argv[2]);

	printf("Problem: route from %d to %d\n\n", start, goal);

	d = ids(start, goal, &nodeCount);

	if (d >= 0){
		printSolution(start, d, nodeCount);
	}

	else {
		printf("Solution not found.\n");
	}

	return 0;
}

// l[] represents lengths of different words in input sequence. For example,
// l[] = {3, 2, 2, 5} is for a sentence like "aaa bb cc ddddd".  n is size of
// l[] and M is line width (maximum no. of characters that can fit in a line)
void solveWordWrap (int l[], int n, int M) {
    // For simplicity, 1 extra space is used in all below arrays

    // extras[i][j] will have number of extra spaces if words from i
    // to j are put in a single line
    int extras[n+1][n+1];

    // lc[i][j] will have cost of a line which has words from
    // i to j
    int lc[n+1][n+1];

    // c[i] will have total cost of optimal arrangement of words
    // from 1 to i
    int c[n+1];

    // p[] is used to print the solution.
    int p[n+1];

    int i, j;

    // calculate extra spaces in a single line.  The value extra[i][j]
    // indicates extra spaces if words from word number i to j are
    // placed in a single line
    for (i = 1; i <= n; i++) {
        extras[i][i] = M - l[i-1];
        for (j = i+1; j <= n; j++)
            extras[i][j] = extras[i][j-1] - l[j-1] - 1;
    }

    // Calculate line cost corresponding to the above calculated extra
    // spaces. The value lc[i][j] indicates cost of putting words from
    // word number i to j in a single line
    for (i = 1; i <= n; i++) {
        for (j = i; j <= n; j++) {
            if (extras[i][j] < 0)
                lc[i][j] = INF;
            else if (j == n && extras[i][j] >= 0)
                lc[i][j] = 0;
            else
                lc[i][j] = extras[i][j]*extras[i][j];
        }
    }

    // Calculate minimum cost and find minimum cost arrangement.
    //  The value c[j] indicates optimized cost to arrange words
    // from word number 1 to j.
    c[0] = 0;
    for (j = 1; j <= n; j++) {
        c[j] = INF;
        for (i = 1; i <= j; i++) {
            if (c[i-1] != INF && lc[i][j] != INF && (c[i-1] + lc[i][j] < c[j])) { 
                c[j] = c[i-1] + lc[i][j];
                p[j] = i;
            }
        }
    }

    printSolution(p, n);
}

void printNextLevel(int arr[], int level) {
	arr[level - 1] = constrainedRandom(VALUES);

	printf("Sequence for level %d is:\n", level);
	printSolution(arr, level);

	clearScreen(DELAY);
}

int printSolution (int p[], int n) {
    int k;
    if (p[n] == 1)
        k = 1;
    else
        k = printSolution (p, p[n]-1) + 1;
    printf ("Line number %d: From word no. %d to %d \n", k, p[n], n);
    return k;
}

int TextEngine::printSolution (int p[], int n)
{
    int k;
    if (p[n] == 1)
        k = 1;
    else
        k = printSolution (p, p[n]-1) + 1;
    cout << "Line number " << k << ": From word no. " << p[n] << " to " << n << endl;
    return k;
}

void Problem::search()
{

	//set current node to root, we start the search at the root
	Node* currentNode = &nodeStorage[0];
	
	//indicate that we have visited the root node of the search tree
	visitedStates.insert(root.state);

	//step 0 is the initial puzzle state
	std::cout << "Step 0: " << currentNode->state << std::endl;
	
	//this loop is essentially going to plow through the queue of nodes and process them
	while(1)
	{
		//check to see if the current state is the goal state
		if(currentNode->state.compare(goalState) == 0)
		{
			//greedy best first search quits as soon as it finds a solution instead of spanning
			//the entire search tree and returning the most optimal solution
			if(currentSearchType == GS)
			{
				//this search is not complete, so we quit here ( as soon as we find a solution )
				storeSolution(currentNode);
				printSolution(solutions.front());
				break;
			}
			else
			{
				//all other search types are complete so we continue searching until the queue finally empties out.
				storeSolution(currentNode);
			}
		}
		
		/*expanding a node: A node essentially represents a puzzle state.  From each puzzle state
		we can reach other adjacent puzzle states by making one move.  When we expand a node,
		we are generating all the adjacent states as nodes, and setting them as children of the 
		current node. In this way, we are storing all the possible puzzle paths as a tree.*/
		expand(currentNode);

		//if there are still nodes in the queue it means that some nodes have not yet
		//been processed.
		if(queue.size() != 0)
		{
			currentNode = chooseNextToExpand();
		}
		else
		{
			//complete search algorithms will end here because the queue is empty, meaning there is nothing else to search
			printBestSolution();
			break;
		}
		
	}
}