#include<conio.h>
#include<iostream.h>
#include<stdio.h>
#define max 20


int n;
int dt[max][max];
int path[20]={-1};
int s=0;

void readfile()
{
   FILE *f;
   f=fopen("E:\\duong.txt","r");
   fscanf(f,"%d",&n);
   for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
         fscanf(f,"%d",&dt[i][j]);
   fclose(f);
}

int kiemtra(int s)
{
   for(int i=0;i<=n;i++)
      if(path[i]==s)
         return i;
   return -1;
}

void xuat()
{
   cout<<"so dinh "<<n;;
   for(int i=1;i<=n;i++)
   {
      cout<<"\n";
      for(int j=1;j<=n;j++)
         cout<<dt[i][j]<<"\t";
   }
}

int next(int s)
{
   int min=100;
   int vitri=1;
   for(int j=1;j<=n;j++)
   {
      if(dt[s][j]>0&&kiemtra(j)<0&&dt[s][j]<min)
      {
         min=dt[s][j];
         vitri=j;
      }
   }
   return vitri;
}

void timduong(int begin)
{
   path[0]=begin;
   int e=begin;
   for(int i=1;i<=n-1;i++)
   {
      int k=next(e);
      path[e]=k;
      s+=dt[e][k];
      e=k;
   }
   path[e]=begin;
}

void xuatduong()
{
   int k=path[0];
   cout<<k<<"\t";
   for(int i=1;i<=n;i++)
   {
      k=path[k];
      cout<<k<<"\t";
   }
}

void main()
{

   clrscr();
   readfile();
   xuat();
   int begin;
   cout<<"\n Nhap dinh bat dau di : ";
   cin>>begin;
   timduong(begin);
   xuatduong();
   cout<<"\n do dai :"<<s;
   getch();

}