/* 9(b). W.A.P. to implement travelling salesperson problem, using dynamic programming for minimum cost tour. */

#include<stdio.h>
#include<conio.h>
int a[10][10],visited[10],n,cost=0;
// To find the next city by least travel charge
int Least(int c)
{
    int i,nc=999,min=999;
    for (i = 0; i < n; i++)
    {
        if ((a[c][i] != 0) && (visited[i] == 0))
        if (a[c][i] < min)
        {
            min = a[c][i];
            nc = i;
        }
    }
    if (min != 999) // if such a next city exists
    cost += min;
    return nc;
}
// There is always an edge(route) from starting city to every other city
// (complete weighted graph), So salesman can come back from any city to
// start point. We are to choose a hamiltonian ckt. of least cost.
// Modelled as DFS
void MinCost(int city)
{
    int i,ncity;
    visited[city] = 1;
    printf("%d -> ",city+1);
    ncity = Least(city); // Find the least cost adjacent city not visited
    if (ncity == 999)
    {
        if (city != 0)
        {
            printf("\nUnable to travel.");
            exit(0);
        }
        ncity = 0; // Go back to start
        printf("%d ",ncity+1);
        cost += a[city][ncity];
        return; // If there are no cities left then salesman has to come back.
    }
    MinCost(ncity);
}
void main()
{
    int i,j;
    clrscr();
    printf("\nEnter no. of cities : ");
    scanf("%d",&n);
    printf("\nEnter the cost matrix :\n");
    for (i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        scanf("%d",&a[i][j]);
        visited[i] = 0;
    }
    printf("\n\nSo the final tour is : ");
    MinCost(0); // Starting from city 0, arbitrary as a cycle is cyclic!
    printf("\nMinimum Cost is %d ",cost);
    getch();
}
/* OUTPUT
Enter no. of cities : 4
Enter the cost matrix :
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0
So the final tour is : 1 -> 4 -> 2 -> 3 -> 1
Minimum Cost is 25
*/