Na planeti X postoji N država i svaka ima po M gradova. Dva grada iz neke države mogu biti povezana jednosmernim putem. Povezanost gradova u nekoj državi određena je težinskom matricom. Ovakva matrica je dimenzija M*M i vrednost u matrici na mestu sa koordinatama (i, j) je dužina (u kilometrima) puta koji vodi od grada i do grada j. Ako ne postoji put koji vodi od grada i do grada j onda je na mestu (i, j) u matrici vrednost 0. Postoje još i međunarodni putevi koji su jednosmerni sa osobinom, da međunarodni put povezuje neki grad iz zemlje i (1 ≤ i ≤ N-1) sa nekim gradom iz zemlje i+1 i to tako da je smer puta od zemlje i ka zemlji i+1. Između bilo koje dve uzastopne zemlje i (1 ≤ i ≤ N-1) i i+1 postoji tačno K međunarodnih puteva. Dužina svakog puta je manja od 10000 kilometara.

Potrebno je startujući iz bilo kog grada na planeti X obići sve gradove na zadatoj planeti tako da se svaki grad poseti tačno jednom i da dužina tako napravljene putanje bude minimalna moguća.

Ulaz:

U prvom redu ulazne datoteke nalaze se tri broja N, M i K međusobno razdvojena razmakom (2 ≤ N ≤ 100, M ≤ 8, K ≤ M²). Zatim je u narednih M redova zadata težinska matrica prve zemlje (u svakom redu po jedna vrsta matrice). U narednih K redova zadate su međunarodne veze između gradova prve i druge zemlje po formatu grad_prve_zemlje grad_druge_zemlje dužina_veze_u_kilometrima. Zatim je zadata težinska matrica druge zemlje pa međunarodne veze između gradova druge i treće zemlje i tako dalje zaključno sa težinskom matricom N te zemlje.

Izlaz:

U prvom i jedinom redu izlazne datoteke treba ispisati dužinu tražene putanje minimalne moguće dužine.

Primer:

2 3 3
0 1 0
0 0 1
4 0 0
1 1 20
2 1 2
3 2 10
0 0 2
0 1 1
1 2 0

11

Objašnjenje:

/*
ZADATAK: drzave
JEZIK: c
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MCON 10

typedef enum{false,true} Bool;
long a[101][MCON][MCON], b[101][MCON][MCON], act[MCON];
long N,M,K,Rez,BrPer;
short GenPer[40500][MCON];
const char *ulaz= "drzave.in";
const char *izlaz="drzave.out";



void Citaj();
void Init();
void Uradi();
void GPer(int);
void GGPer();
void Ispisi();

int main(){

  Init();
  Citaj();
  GGPer();
  Uradi();
  Ispisi();
  return 0;
}

void Ispisi(){
  FILE *fout=stdout;//fopen(izlaz,"w");
  fprintf(fout,"%ld",Rez);
//    fclose(fout);
}
void Uradi(){
  int i,j,l;
  long min;

  for(i=N;i>0;i--){
    GPer(i);  //nakon GPer u act se nalaze minimalne duzine putanja od
          //bilo kog grada drzave i.

    for(j=1;j<=M;j++){a[i-1][M+1][j]=0; a[i-1][j][M+1]=0;}

    for(j=1;j<=M;j++)
      for(l=1;l<=M;l++)
        if(b[i-1][j][l]>0 && act[l]>0) {
          if (a[i-1][j][M+1]==0){a[i-1][j][M+1]=b[i-1][j][l]+act[l];}
          else {
            if (a[i-1][j][M+1]>b[i-1][j][l]+act[l]) 
              a[i-1][j][M+1]=b[i-1][j][l]+act[l];
          }
        }
    if (i!=1) for(j=1;j<=M+1;j++) act[j]=0;
  }
  min=0;
  for(i=1;i<=M;i++)
    if((act[i]>0) &&((min>act[i])||(min==0))) min=act[i];
  Rez=min;
}

void GPer(int broj){
  long per[MCON];
  Bool ok;
  int i,j;
  long zbir,br=0;

  for(i=0;i<BrPer;i++){
    for(j=1;j<=M+1;j++) per[j]=GenPer[i][j];
    //provera da li je putanja moguca
    zbir=0; ok=true;
    for(j=2;j<=M+1;j++)
      if ((a[broj][per[j-1]][per[j]]>0)||(a[broj][per[j-1]][per[j]]==0 && j==M+1 && broj==N) )
        zbir+=a[broj][per[j-1]][per[j]];
      else ok=false;
    if ((ok==true)&&(((act[per[1]]>zbir)&&(act[per[1]]!=0))||(act[per[1]]==0))) {
      act[per[1]]=zbir;
    }
    //kraj provere
  }
}
void GGPer(){
  short per[MCON];
  Bool bio[MCON], ok;
  int i,j,k,l;

  for(i=1;i<=M+1;i++) {per[i]=i; bio[i]=true;}
  BrPer=0;

  for(;;){
    for(i=1;i<=M+1;i++) GenPer[BrPer][i]=per[i];
    BrPer++;
    //sledeca permutacija
    k=M; ok=false;
    while((k>0)&&(ok==false)){
      for(i=per[k]+1;i<=M;i++)
        if(bio[i]==false) {
          bio[per[k]]=false;
          per[k]=i;
          bio[i]=true;
          ok=true;
          for(j=k+1;j<=M;j++)
            for(l=1;l<=M;l++)
              if(bio[l]==false){
                bio[l]=true; per[j]=l;
                break;
              }
        }
        if (ok==false){
          bio[per[k]]=false;
          per[k]=0; k--;
        }
    }
    if (k==0) break;
  }
}

void Init(){
  int i,j,l;

  for(i=1;i<=M;i++) {
    act[i]=0; a[N][i][M+1]=0; a[N][M+1][i]=0;
  }
  for(i=1;i<=N;i++)
    for(j=1;j<=M;j++)
      for(l=1;l<=M;l++){ 
        a[i][j][l]=0;
        if (i<N) b[i][j][l]=0;
      }
}

void Citaj(){
  FILE *fin=stdin;//fopen(ulaz,"r");
  int g1,g2,d,i,j,l;

  fscanf(fin,"%d%d%d",&N,&M,&K);
  for(i=1;i<=N;i++){
    for(j=1;j<=M;j++)
      for(l=1;l<=M;l++) fscanf(fin,"%d",&a[i][j][l]);
    if(i!=N){
      for(j=0;j<K;j++){
        fscanf(fin,"%d%d%d",&g1,&g2,&d);
        b[i][g1][g2]=d;
      }
    }
  }
//    fclose(fin);
}