#include <iostream>
#include<fstream>
#include<conio.h>
using namespace std;
int A[11][11],n,stiva[20],k=0,m=1000,gasitt[20],suma=20000,l=0;int v,t;

int citire();
void parcurgere(int x, int y, int z);

int  main()
{
citire(); 
cout<<"Matricea A este:"<< endl;
for (int i=1;i<=n;i++)
{for (int j=1;j<=n;j++) 
     cout<<A[i][j];
 cout<<endl;
}

cout<<"Nodul de pornire este:";cin>>v;cout<<endl;
cout<<"Nodul destinatie este:";cin>>t;cout<<endl;
parcurgere(t,v,0);

cout<<"Drumul cel mai optim este:"<<v<<" ";
for(int i=1;i<=l;i++)
cout<<gasitt[i]<<" ";
suma=10000;l=0;
getch();
return 0;
}

int citire(){   ifstream f("in.txt"); f>>n;
				for (int i=1;i<=n;i++)
					for(int j=1;j<=n;j++)
						f>>A[i][j];
				return 0;}


int verificare(int x,int z, int y){
	if (z==0) return 0;
	if (y==x) return 1;
    for(int i=1;i<=z;i++)
	   {if (stiva[i]==x) return 1;
	    if (i==z) return 0;
	    }}

void gasit(int z, int x){
int q=0;
for (int i=1;i<z;i++)
    q+=A[stiva[i]][stiva[i+1]];
q+=A[v][stiva[1]];
if(q<suma&&q!=0)
    {suma=q;l=z;
    for(int j=1;j<=z;j++)
    gasitt[j]=stiva[j];
}}

void parcurgere(int x, int y, int z){
 if(x==y) gasit(z,y);
 else {for (int i=1;i<=n;i++)
 {
            {if (A[i][y]!=0)
	             if(verificare(i,z,y)==0)
		              {stiva[z+1]=i;
		               parcurgere(x,i,z+1);}}}}}