#include<stdio.h>
 
int matrix[25][25], visited_cities[10], limit, cost = 0;
 
int tsp(int c)
{
      int count, nearest_city = 999;
      int minimum = 999, temp;
      for(count = 0; count < limit; count++)
      {
            if((matrix[c][count] != 0) && (visited_cities[count] == 0))
            {
                  if(matrix[c][count] < minimum)
                  {
                        minimum = matrix[count][0] + matrix[c][count];
                  }
                  temp = matrix[c][count];
                  nearest_city = count;
            }
      }
      if(minimum != 999)
      {
            cost = cost + temp;
      }
      return nearest_city;
}
 
void minimum_cost(int city)
{
      int nearest_city;
      visited_cities[city] = 1;
      printf("%d ", city + 1);
      nearest_city = tsp(city);
      if(nearest_city == 999)
      {
            nearest_city = 0;
            printf("%d", nearest_city + 1);
            cost = cost + matrix[city][nearest_city];
            return;
      }
      minimum_cost(nearest_city);
}
 
int main()
{ 
      int i, j;
      scanf("%d", &limit);
      for(i = 0; i < limit; i++)
      {
             for(j = 0; j < limit; j++)
            {
                  scanf("%d", &matrix[i][j]);
            }
            visited_cities[i] = 0;
      }
      printf("Path: ");
      minimum_cost(0);
      printf("\nMinimum Cost: \t");
      printf("%d\n", cost);
      return 0;
}

• Problem Description
  Travelling Salesman Problem (TSP) is a touring problem in which n cities and distance between each pair is given. We have to find a shortest route to visit each city exactly once and come back to the starting point.
  
  
  Input
  
  First line contains an integer N = number of cities
  Enter the cost matrix
  
  Output
  
  Output an optimal path and the minimum cost.
• Test Case 1
  Input (stdin)4
  1 5 4 2
  2 1 5 4
  9 6 2 4
  7 5 3 2
  Expected OutputPath: 1 4 3 2 1
  Minimum Cost: 13
• Test Case 2
  Input (stdin)4
  1 2 3 4
  5 6 7 8
  3 4 5 6
  9 8 4 3
  Expected OutputPath: 1 4 3 2 1
  Minimum Cost: 17