#include<stdio.h>   // pour printf
#include<stdlib.h>  // pour exit et calloc
#include<time.h>    // pour clock
#define N 299       // nombre de villes
long d[N][N];       // d[i][j] est la distance de la ville i à la ville j
int n=N, nx[N], ny[N];  // pour 0<=i,j<n  d[i][j]=d0[nx[i]][ny[i]]  où d0 est la valeur initiale de d 
struct { long v; int sui[N]; } opti, S;   // sui[i]=j si l'arc i-->j est imposé, v=\sum d0[i][sui[j]]
// Dans le sous-problème courant, S, le nombre d'arcs imposés est N-n et v doit être ajouté à la valeur de la solution.
// Dans la meilleure solution réalisable trouvée, opti, tous les arcs sont imposés (comme si n=0) et v est donc la valeur. 
typedef struct { long v; int i, j; } sep; // v=évaluation par défaut. La séparation se fera en prenant ou non l'arc i-->j
typedef long unsigned lu;                 // (lu)a<10lu   <==>  a<10 && a>=0
lu blog(lu a) { asm("bsr %0,%0" : "+r"(a) ); return a; } // blog((1<<5) + (1<<7))=7   blog(0)=0  avec gcc et x86 ou x86-64
lu val2(lu a) { asm("bsf %0,%0" : "+r"(a) ); return a; } // val2((1<<5) + (1<<7))=5   val2(0)=0
long min(long a, long b) { return a<b?a:b; }
#define mins(x) asm("cmp %1,%0; cmovge %1,%0" : "+r"(s) : "r"(x) : "cc")  // s=min(s,x)  inutile avec -O3
#define swap(a,b) ({ typeof(a) c=a; a=b, b=c; })  // échange efficacement les valeurs de a et b avec -O3
const long inf=(~0lu>>1)/N; // =maxlongint/N, valeur maximale de l'infini, pour que N*inf ne déborde pas
void afft(int*t, int n) { while(n--) printf(" %d",*t++); printf("\n"); }
void affnxny() { printf("numéro des lignes   :"), afft(nx,n), printf("numéro des colonnes :"), afft(ny,n); }
void affd(int n) { int i,j; for(i=0;printf("\n"),i<n;i++) for(j=0;j<n;j++) printf("%14ld",d[i][j]); }
void aff(typeof(S) S)
{ int i;
  printf("suivants imposés :"); for(i=0;i<N;i++) if(S.sui[i]>=0) printf(" %d->%d",i,S.sui[i]);
  printf("\nv=%ld\n",S.v);
}
long hongrois(int n, long d[n][N], int a[n])  // return min \sum_i d[i][a[i]] 
{ long x[n], y[n], mi[n], s;
  int b[n], i0, i, j;
  long f(int i,int j) { if((lu)i>=(lu)n || (lu)(j)>=(lu)n) printf("raté i=%d j=%d\n",i,j); return d[i][j]-x[i]-y[j]; }
  for(i=n;i--;) a[i]=b[i]=-1, x[i]=y[i]=~0lu>>1;
  for(j=n;j--;) for(i=n;i--;) y[j]=min(y[j],d[i][j]);
  for(i=n;i--;) for(j=n;j--;) x[i]=min(x[i],d[i][j]-y[j]);
  for(i0=n;i0--;)
  { int xm[n], ym[n], p[n], ip=0;
    for(j=n;j--;) mi[j]=f(i0,j), xm[j]=ym[j]=-1;
    xm[p[ip++]=i0]=n;
    while(j<0) if(ip)
     for(i=p[--ip],j=n;j--;)
      if(ym[j]>=0) ; else
      if(f(i,j)) mi[j]=min(mi[j],f(i,j)); else
      if(b[j]<0) break; else
      xm[p[ip++]=b[j]]=j, ym[j]=i;
               else  
    { for(s=~0lu>>1,j=n;j--;) if(ym[j]<0) s=min(s,mi[j]);
      for(j=n;j--;) if(ym[j]<0) y[j]+=s, mi[j]-=s;
      for(i=n;i--;) if(xm[i]<0) x[i]-=s;
      for(j=n;j--;) if(ym[j]<0 && !mi[j])
       { for(i=n;xm[--i]<0 || f(i,j);) ;
         if(b[j]<0) break; else
         xm[p[ip++]=b[j]]=j, ym[j]=i;
       }
    }
    for(;b[a[i]=j]=i,i!=i0;i=ym[j]) j=xm[i];
  }
  for(s=0,i=n;i--;) s+=d[i][a[i]]; 
  for(i=n;i--;) for(j=n;j--;) d[i][j]-=x[i]+y[j];
  for(i=n;i--;) for(j=n;j--;) if(d[i][j]<0) printf("f(%d,%d)=%ld\n",i,j,d[i][j]), exit(1);
  for(i=n;i--;) if((lu)a[i]>=(lu)n) printf("a[%d]=%d\n",i,a[i]), exit(1);
  for(j=n;j--;) if((lu)b[j]>=(lu)n) printf("b[%d]=%d\n",j,a[j]), exit(1);
  for(i=n;i--;) if(a[b[i]]!=i) printf("a[b[%d]=%d]=%d\n",i,b[i],a[b[i]]), exit(1);
  for(i=n;i--;) if(d[i][a[i]]) printf("f(%i,a[%i])=%ld\n",i,i,d[i][a[i]]), exit(1);
  return s;
}
void minore(int n,long D[N][N],sep*s)
{ int i, j, k, ii=0, jj=0, ncy=-1, nc[N], lc[N], a[N];
  long f[N][N], e[N][N], p=-1, mx[N], my[N];
  for(i=n;i--;) for(j=n;j--;) f[i][j]=D[i][j];  // D n'est pas modifié, mais f oui.
  for(i=n;i--;) f[i][i]=inf, nc[i]=-1, lc[i]=0; // interdit les arcs i-->i
  if(opti.v<=(s->v+=hongrois(n,f,a))) return;   // si l'évaluation est déja trop grande ou infinie
  for(i=n;i--;) if(nc[i]<0) for(ncy++;nc[i]<0;i=a[i]) lc[nc[i]=ncy]++; // comptage des cycles et de leurs longueurs
  if(!ncy && d==D) for(opti=S, opti.v=s->v,i=n;i--;) opti.sui[nx[i]]=ny[a[i]]; // 1 cycle sans appel récursif de minore : opti=S
  if(!ncy++) return;     // 1 cycle : l'évaluation est optimale (pour ce niveau de récursion)
  for(i=ncy;i--;) for(j=ncy;j--;) e[i][j]=~0lu>>1;
  for(i=n;i--;) for(j=n;j--;) ii=nc[i], jj=nc[j], e[ii][jj]=min(e[ii][jj],f[i][j]); // on fusionne chaque cycle en un seul sommet
  for(j=ncy;j--;) for(i=ncy;i--;) for(k=ncy;k--;) e[i][k]=min(e[i][k],e[i][j]+e[j][k]); // Floyd-Warshall
  minore(ncy,e,s);  // s-->v+= évaluation pour le graphe réduit
  if(s->v>=opti.v || d!=D) return;  // si l'évalution est trop grande ou si on est dans un appel récursif de minore
  for(jj=0,ii=ncy;ii--;) if(lc[ii]<lc[jj]) jj=ii;  // jj est le cycle le plus court
  for(i=n;i--;) mx[i]=my[i]=f[i][a[i]]=inf;   // On élimine les arcs des cycles pour le calcul du miminum
  for(i=n;i--;) for(j=n;j--;) mx[i]=min(mx[i],f[i][j]), my[j]=min(my[j],f[i][j]); // mx[i]=min f[i][j]  my[j]=min f[i][j]
  for(i=n;i--;) if(nc[i]==jj) if(mx[i]+my[a[i]]>p) p=mx[s->i=i]+my[s->j=a[i]];//on choisit i sur le plus court cycle qui maximise mx[i]+my[a[i]]
}
void eval(sep*s) { s->v=S.v, minore(n,d,s); } 
void separevalprof(sep s)
{ long dsisj=inf;
  void sep1() { swap(dsisj,d[s.i][s.j]); }  // met d[s.i][s.j] à l'infini pour interdire s.i->s.j ou le remet à sa valeur initiale
  void sep2()  // force s.i->s.j
  { int i;
    S.sui[nx[s.i]]=ny[s.j];  // l'arc s.i-->s.j correspond à l'arc nx[s.i]-->ny[s.j] de d0.
    S.v+=d[s.i][s.j];
    for(i=n;i--;) swap(d[s.i][i],d[s.j][i]); swap(nx[s.i],nx[s.j]); // La ligne s.i est remplacée par la ligne s.j qui est remplacée
    for(i=n;i--;) swap(d[s.j][i],d[n-1][i]); swap(nx[s.j],nx[n-1]); // par la dernière ligne n-1 où on range l'ancienne ligne s.i
    for(i=n;i--;) swap(d[i][s.j],d[i][n-1]); swap(ny[s.j],ny[n-1]); // La colonne s.j est remplacée par la dernière colonne où on range ...
    n--;  // La matrice a donc une ligne et une colonne de moins
  }
  void tep2()  // défait sep2()
  { int i;
    n++;
    for(i=n;i--;) swap(d[i][s.j],d[i][n-1]); swap(ny[s.j],ny[n-1]);
    for(i=n;i--;) swap(d[s.j][i],d[n-1][i]); swap(nx[s.j],nx[n-1]);
    for(i=n;i--;) swap(d[s.i][i],d[s.j][i]); swap(nx[s.i],nx[s.j]);
    S.v-=d[s.i][s.j];
    S.sui[nx[s.i]]=-1;
  }
  if(s.v>=opti.v) return;
  sep s1,s2;
  sep1(), eval(&s1), sep1(),  // On évalue le sous-problème obtenu en interdisant s.i-->s.j
  sep2(), eval(&s2), tep2();  // On évalue le sous-problème obtenu en forçant s.i-->s.j
  int i=s2.v<s1.v, j;  // On traite chacun des 2 sous-problèmes en commençant par le plus prometteur : min(s1.v,s2.v)
  for(j=2;j--;) if(i^j) sep1(), separevalprof(s1), sep1();
                else    sep2(), separevalprof(s2), tep2();
}
void separeval() { sep s; opti.v=inf, eval(&s), separevalprof(s); }
/* pour tout k dans l'ensemble I faire xxx   a 2 traductions :
   pour tout k dans [0,N-2] faire si k est dans I alors xxx      for(k=N-1;k--;) if(I&1<<k) xxx           avec if
   K=I; tant que K est non vide faire { k=min K; xxx ; K-={k} }  for(K=I;K;K-=1<<k) { k=val2(K); xxx }    sans if */
void progdyn() // mémoire : Nx2^N    temps : NxNx2^N
{ int n1=N-1, nn=1<<n1, nn1=nn-1, I, j=0, k, J, K;
  long (*f)[n1]=calloc(nn/2,sizeof(*f)), s;  // long f[1<<(N-2)][N-1]; ne tient pas dans la pile 
  if(!f) { printf("mémoire insuffisante pour la programmation dynamique\n"); return; }
  long *g(int I) { return f[I<nn1-I?I:nn1-I]; }
  for(k=n1;k--;) g(1<<k)[k]=d[k][n1];                   // g({k})[k]=e[N-1](k)
  if(1) for(I=0;I<nn;I++) for(K=I;K;K&=K-1,g(I)[k]=s)   // version sans if, donc plus rapide
        for(k=val2(K),J=I^1<<k,s=J?~0lu>>1:d[k][n1];J;J&=J-1) j=val2(J), s=min(s,g(I^1<<k)[j]+d[k][j]);
  else  for(I=0;I<nn;I++) if(I&(I-1)) for(k=n1;k--;) if(I&1<<k) for(g(I)[k]=~0lu>>1,j=n1;j--;)
        if(I&1<<j && j!=k) g(I)[k]=min(g(I)[k],g(I^1<<k)[j]+d[k][j]);  // g(I)[k]=min{g(I-{k})[j]+e[j][k] | j dans I-{k}}
  s=~0lu>>1;
  for(k=n1;k--;) if(f[0][k]+d[n1][k]<s) s=f[0][k]+d[n1][j=k];  // opti.v=s=min{g({0,1,....N-2})[k]+e[k][N-1] | 0<=k<N-1}
  opti.v=s;  // On utilise la transposée e de d, plutôt que d, pour que la boucle interne soit sur le deuxième indice
  opti.sui[n1]=j;
  for(I=nn1;(K=I^1<<j);j=opti.sui[j]=k,I=K) for(k=n1;!(K&1<<--k) || g(K)[k]+d[j][k]!=g(I)[j];) ;  // g(I-{j})[k]+e[k][j]=g(I)[j]
  opti.sui[j]=n1;
  free(f);
}
void afftemps()  // affiche le temps écoulé en secondes entre deux appels à afftemps, s'il est non nul.
{ static lu t=0; lu u=clock(), d=u-t;
  if(d) printf(" %ld.%06ld\n",d/1000000lu,d%1000000lu), t=u;
}
int main()
{ int i, j, z=0;
  for(i=N;i;i--) for(j=N;j;j--) d[i-1][j-1]=(z=101*z+1)&((1<<25)-1);
  S.v=0;
  for(i=N;i--;) nx[i]=ny[i]=i, S.sui[i]=-1;
  aff(S), afftemps();
  printf("début des calculs\n");
  if(N<300) printf("\nséparation et évaluation en profondeur\n"), separeval(), aff(opti), afftemps();
  if(N< 23) printf("\nprogrammation dynamique\n"),                progdyn(),   aff(opti), afftemps();
  return 0;
}