Travelling salesman

class Tsp {
  static int cities=15; 
  /*    
  static int dist[][] = 
         {{0, 5, 4, 3},              
          {5, 0, 2, 9},           
          {4, 2, 0, 6},           
          {3, 9, 6, 0}};
  */        
  static int dist[][] =  {
   {0,92,85,178,206,105,121,223,160,12,183,179,26,220,233,184,151,210,224,231,126,216,161,217,178,156,13,131,271,265,89,107,203,90,146,70,224,185,144,183,166,179,244,69,60,247,196,152,156,111,211,43,94,71,36,144,67,123,94},
   {92,0,68,270,298,197,137,213,131,80,250,272,118,245,223,95,243,231,317,323,218,268,72,268,89,147,105,223,261,255,40,171,295,138,57,162,242,206,218,276,77,271,234,161,125,340,265,191,216,84,304,54,159,37,100,237,132,34,158},
   {85,68,0,262,290,189,90,167,84,72,204,235,111,199,177,117,236,184,309,315,210,222,103,221,120,100,97,216,215,209,22,136,258,92,61,154,196,160,190,268,94,228,188,153,93,332,219,145,170,37,296,42,141,60,69,229,117,64,135},
   {178,270,262,0,31,175,219,265,280,190,138,76,152,233,256,347,84,208,158,56,50,168,339,120,356,255,171,66,312,306,266,153,93,189,293,108,237,199,91,9,312,82,285,123,183,73,99,202,196,249,145,221,141,249,204,78,170,300,149},
   {206,298,290,31,0,203,250,296,311,218,170,107,180,264,287,378,118,239,103,25,78,199,367,151,384,286,199,97,343,338,294,185,124,221,325,136,269,231,122,22,344,113,317,151,215,42,130,234,227,280,58,249,172,277,232,106,201,328,181},
   {105,197,189,175,203,0,216,302,256,117,222,176,79,270,293,288,148,260,221,228,123,261,266,214,283,248,98,128,349,343,193,153,200,185,234,67,274,235,152,180,265,176,322,66,140,244,193,202,206,209,208,148,140,176,131,141,162,227,106},
   {121,137,90,219,250,216,0,104,62,119,120,173,136,136,114,152,237,101,309,275,211,138,162,138,179,37,133,154,152,146,96,74,196,30,102,158,133,76,128,228,116,165,125,148,76,292,150,61,86,53,297,121,78,139,85,230,56,124,107},
   {223,213,167,265,296,302,104,0,96,221,149,193,239,32,10,219,310,60,384,322,276,128,239,153,256,71,236,233,48,42,173,149,217,133,179,244,29,67,212,274,183,186,21,234,178,338,165,97,95,130,371,198,162,216,188,304,158,201,196},
   {160,131,84,280,311,256,62,96,0,158,181,233,177,128,106,136,297,124,370,336,271,162,156,186,174,29,172,214,144,138,91,134,257,91,96,215,125,100,189,289,100,226,117,206,137,353,198,122,147,47,357,115,139,133,125,290,117,118,167},
   {12,80,72,190,218,117,119,221,158,0,181,192,38,218,231,172,163,208,237,243,138,214,149,229,166,154,25,143,269,263,76,105,215,89,133,82,223,183,142,196,154,191,242,81,58,260,208,150,154,99,224,31,92,59,34,157,65,110,92},
   {183,250,204,138,170,222,120,149,181,181,0,67,199,117,140,266,183,92,257,195,149,52,276,26,293,156,196,96,196,191,210,80,90,115,216,157,122,84,70,147,229,59,170,170,138,211,38,72,66,167,244,209,94,237,148,177,118,237,128},
   {179,272,235,76,107,176,173,193,233,192,67,0,154,161,184,301,125,136,198,132,90,96,307,48,324,208,173,50,240,235,241,108,24,143,247,112,166,128,58,85,266,8,214,125,157,149,26,131,125,202,185,222,108,250,166,118,137,269,119},
   {26,118,111,152,180,79,136,239,177,38,199,154,0,236,249,210,125,226,199,205,100,232,187,191,204,172,19,105,287,281,115,123,177,106,172,44,240,201,129,158,192,153,260,43,76,222,170,168,172,130,186,69,110,97,52,119,83,149,82},
   {220,245,199,233,264,270,136,32,128,218,117,161,236,0,23,251,278,36,352,289,244,96,270,121,288,103,233,201,79,73,205,117,185,164,211,212,4,35,180,242,215,154,52,202,210,306,133,65,63,162,339,230,130,248,185,272,156,232,164},
   {233,223,177,256,287,293,114,10,106,231,140,184,249,23,0,229,301,51,375,313,267,119,249,144,266,81,246,224,57,51,183,140,208,143,189,235,20,58,203,265,193,177,30,225,188,329,156,88,86,140,362,208,153,226,198,295,168,211,187},
   {184,95,117,347,378,288,152,219,136,172,266,301,210,251,229,0,335,246,408,403,309,284,95,283,112,153,197,282,267,261,95,202,324,157,54,253,248,222,256,356,36,293,241,252,198,420,285,206,232,100,395,141,206,134,173,328,184,62,232},
   {151,243,236,84,118,148,237,310,297,163,183,125,125,278,301,335,0,253,73,121,34,213,312,165,329,272,144,89,357,352,240,176,148,206,281,81,283,245,115,90,311,127,331,96,164,77,144,226,230,255,60,194,163,222,177,7,185,274,130},
   {210,231,184,208,239,260,101,60,124,208,92,136,226,36,51,246,253,0,326,264,219,71,256,95,273,99,223,175,107,101,190,107,159,123,196,203,40,24,154,217,210,129,80,193,164,281,107,54,54,147,313,215,121,233,175,246,145,218,155}                
  };            
  static int path[] = new int[cities];
  static int bestpath[] = new int[cities];
  static int calledcount=0;        
  static int passedcount=0;          
  static int pathcount=0;         
  static int bestlen=999999999;          
          
  public static void main(String[] args) {
    int res;
    int i;
      
    System.out.println("tsp starts");          
    res=searchcities(0,0,0);
    System.out.println("----------------------------");  
    System.out.println("best cost: "+res);
    System.out.print("best   path:");  
    for(i=0;i<cities;i++) {
        System.out.print(" "+bestpath[i]);  
    }    
    System.out.println();
    System.out.println("done    paths: "+pathcount);  
    System.out.println("done    calls: "+calledcount);  
    System.out.println("passed cities: "+passedcount);            
  } 

  public static int searchcities
            (int curcity, int passedcities, int passedlen) {
    int j;  
    int newcity;  
    int tmpres;
    int bestres;  
    boolean usedcityflag;  
    boolean nogoflag;            
    int tmp;
                
    calledcount++;            
    // just print
    /*
    System.out.println();  
    for(j=0;j<passedcities;j++) System.out.print("  ");        
    System.out.println
       ("searchcities curcity: "+curcity+
        " passedcities:"+passedcities+
        " passedlen: "+passedlen);
    */            
    // maybe reached last city?  
    if (passedcities>=cities-1) {
     pathcount++;   
     tmp=passedlen+dist[curcity][0];
     if (tmp<bestlen) { 
        bestlen=tmp;
        path[passedcities]=curcity; 
        for(j=0;j<cities;j++) bestpath[j]=path[j];
     }    
     return tmp;   
    }    
    
    passedcount++;    
    path[passedcities]=curcity;  
    bestres=99999999;  
    // loop over all cities  
    for(newcity=0;newcity<cities;newcity++) {
      // search whether we have been in newcity  
      usedcityflag=false;  
      for(j=0;j<=passedcities;j++) {
        if (path[j]==newcity) {
          usedcityflag=true;  
          break;            
        }    
      }         
      if (!usedcityflag) {       
         // compute path length  
         //for(j=0;j<passedcities;j++) System.out.print("  ");
         //System.out.print("going to city "+newcity+" ");
         nogoflag=false;          
         if (passedcities==cities-2) {
           // last city
           if (bestlen<=
               (passedlen+dist[curcity][newcity]+ 
                          dist[newcity][0]))  
              nogoflag=true;  
         } else {             
           // not last city  
           if (bestlen<=
               (passedlen+dist[curcity][newcity])) nogoflag=true;          
         }          
         if (!nogoflag) {
           tmpres=
             searchcities
               (newcity,
                passedcities+1,
                passedlen+dist[curcity][newcity]); 
           //System.out.println("giving length "+tmpres); 
           // store length if shorter than bestres
           if (tmpres<bestres) bestres=tmpres;  
         }    
      }    
    }       
    return bestres;    
  }       

}