#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
#define INF 9999

int graph[20][20],tpath[20],path[20];
int pi=1,min=INF,mmin;


void swap(int *a,int *b)
{ 
    int temp; 
    temp=*a,*a=*b,*b=temp;
}

int find_cost(int n)
{
    int i,cost=0; 
    int j=1; 

    for(i=1;i<=n;i++) 
    { 
        if(graph[tpath[j]][tpath[j+1]]==INF || cost>min ) 
            return INF; 

            cost+=graph[tpath[j]][tpath[j+1]]; 
            j++;
    } 
    return cost;
}
void perm(int k,int m,int n)
{ 
    int i,j; 
    if(k==m) 
    { 
        mmin=find_cost(n); 
        if(mmin<min)
        { 
            min=mmin; 
            for(j=1;j<=n+1;j++) 
                path[j]=tpath[j]; 
        } 
    } 
    else 
    { 
        for(i=k;i<=m;i++) 
        {
            swap(&tpath[k],&tpath[i]); 
            perm(k+1,m,n); 
            swap(&tpath[k],&tpath[i]);
         }
    }
}
void main()
{
    int n,i,j,root;
    clrscr();
    cout<<"\nEnter the no. of vertices : ";
    cin>>n;
    cout<<"\nEnter the adjacency matrix: ";
    for (i = 1;i <= n; i++)
    for (j = 1; j <= n; j++)
    {
        cin>>graph[i][j];
        if (graph[i][j] == 0)
            graph[i][j] = INF;
    }
    cout<<"\nEnter the starting vertex: ";
    cin>>root;
    for (i = root; i <= n; i++)
        tpath[pi++]=i;
    for (i = 1; i <= root; i++)
        tpath[pi++]=i;
        perm(2,n,n);
        cout<<"\nThe path is : \n";
    for (i = 1; i <= n+1; i++)
        cout<<path[i]<<"\t";
        cout<<"\nCost of this path is: "<<min<<endl;
        getch();
}
/* OUTPUT
Enter the number of vertices : 4
Enter the adjacency matrix :
0 30 6 4
30 0 5 10
6 5 0 20
4 10 20 0

Enter the starting vertex: 1
The path is :
1-->3-->2-->4-->1
Cost of this path is: 25
*/