//Trezorier
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#define N 100

int x[2*N],r[2*N],costmin=32767,o[N],p[N],c[N][N],xi,xf,n,dat;
int Verif(int k)
{ int i,j ;
  for(i=1;i<k;i++)
  for(j=i+2;j<k;j++)
    if(x[i]==x[j]&&x[i+1]==x[j+1]) return 0;
  if(c[x[k-1]][x[k]] ==0 )return 0;
  return 1;
}
int drum(void)
{ int vb,i,k,cost,nrv,nr=0;
  x[1]=xi;k=2;x[k]=0;cost=0;nrv=0;
  while(k>1)
  { vb=0;
    while(x[k]<n)
    { x[k]++;
      vb=Verif(k);
      if(vb){  cost+=c[x[k-1]][x[k]];
	       for (i=1;i<=dat;i++)
		 if(x[k]==o[i])if(p[i]==0){p[i]=1;nrv++;}
			       else p[i]++;
	       break;}
    }
    if (vb==1&&nrv==dat&&x[k]==xf)
    {  if(costmin >cost ){for(i=1;i<=k;i++) r[i]=x[i];
			  costmin=cost;
			  nr=k;}
       cost-=c[x[k-1]][x[k]];

    }
    else if(vb) { k++;x[k]=0;}
	 else { k--;
		cost-=c[x[k-1]][x[k]];
		for (i=1;i<=dat;i++)
		 if(x[k]==o[i])if(p[i]==1){p[i]=0;nrv--;}
			       else p[i]--;}
  }
if(nr==0) {printf("Nu se poate realiza ruta!");getch();exit(1);}
return nr;
}
void main (void)
{ int i,k,j;
  //clrscr();
  printf("\t\tTrezorierul\n");
  printf("n=");
  scanf("%d",&n);
  printf("Orasul initial:");
  scanf("%d",&xi);
  printf("Orasul final:");
  scanf("%d",&xf);
  i=0;dat=0;
  do{
  i++;
  printf("Oras cu datorie:");
  scanf("%d",&o[i]);
  }while(o[i]!=0);
  dat=i-1;
/*  c[1][2]=c[2][1]=6;
  c[2][3]=c[3][2]=3;
  c[2][4]=c[4][2]=2;
  c[4][5]=c[5][4]=2;
  c[4][6]=c[6][4]=10;
  c[5][6]=c[6][5]=4;
  c[6][7]=c[7][6]=5;*/
  for(i=1;i<=n;i++)
  for(j=i+1;j<=n;j++)
  { printf("c[%d][%d]=",i,j);
    scanf("%d",&c[i][j]);
    c[j][i]=c[i][j];}
  k=drum();
  printf("\nCostul minim =%d",costmin);
  for(i=1;i<=k;i++) printf("\n%d",r[i]);
  getch();
}