/* Bare backtracking solution to the Traveling Salesman Problem:
 * at each vertex, traverse the available edges, passing along a
 * permutation vector, new cell, and total distance traveled so far
 * --- if there is no solution yet OR the distance so far is less
 * than the present solution.
 *
 * Input file expectation:
 *   Number of vertices in the graph (crossroads in the map)
 *   That many lines giving names
 *   one blank line
 *   Lines specifying roads:  two double-quoted names and an integer
 *
 * Language:  Java 1.5.x due to Scanner, PriorityQueue, . . .
 *
 * Author:  Timothy Rolfe
 */
import java.util.*;     // Arrays and Collections and . . .

public class Bound1_TSP_A
{  static int[][]  wt;                 // Matrix of edge weights
   static String[] city;               // Vector of city names
   static int      n;                  // Dimension for wt and city
   static int[]    minAdditionalCost;  // Lowest weight edge out
   static int[]    solution;           // Best tour so far
   static int      tourCost;
   static boolean  DEBUG = false;

   // For debugging convenience:  show state
   private static void partial(int[] vect, int index)
   {  int dist = index == n ? wt[vect[n-1]][vect[0]] : 0;

      System.out.print (city[vect[0]]);
      for ( int k = 1; k < index; k++ )
      {  System.out.print (", " + city[vect[k]]);
         dist += wt[vect[k-1]][vect[k]];
      }
      System.out.println(" for " + dist);
   }

   // Initialize the global variables based on the file passed through
   // the Scanner inp.  See the header documentation for the
   // specifications for the input file.
   private static void init(Scanner inp)
   {  int sub1,
          sub2;
      String line;

      n = inp.nextInt();
      wt = new int[n][n];    // Accept the zero-fill
      city = new String[n];
      solution = new int[n];
      minAdditionalCost = new int[n];
      // Insure the first edge initializes minAdditionalCost
      Arrays.fill(minAdditionalCost, Integer.MAX_VALUE);

      inp.nextLine();   // Discard rest of first line
      for ( sub1 = 0; sub1 < n; sub1++ )
         city[sub1] = inp.nextLine();
      Arrays.sort(city);     // Just to be sure (binarySearch)

      inp.nextLine();   // Discard blank spacing line;

      while ( inp.hasNext() )
      {  int    head, tail;
         int    dist;
         String src, dst;

         line = inp.nextLine();   // E.g.:  "George" "Pasco" 91
         // Chop out the double-quoted substrings.
         head = line.indexOf('"') + 1;
         tail = line.indexOf('"', head);
         src = line.substring(head, tail);

         head = line.indexOf('"', tail+1) + 1;
         tail = line.indexOf('"', head);
         dst = line.substring(head, tail);

         dist = Integer.parseInt( line.substring(tail+1).trim() );
         sub1 = Arrays.binarySearch(city, src);
         sub2 = Arrays.binarySearch(city, dst);
         wt[sub1][sub2] = wt[sub2][sub1] = dist;
      }
      // Find minimum weight edge out of each vertex
      for (sub1 = 0; sub1 < n; sub1++)
         for (sub2 = 0; sub2 < n; sub2++ )
            if ( wt[sub1][sub2] > 0 )  // I.e., edge exists
               if (minAdditionalCost[sub1] > wt[sub1][sub2])
                   minAdditionalCost[sub1] = wt[sub1][sub2];
   }

   // Public access for generating the tours.
   // Generate the initial permutation vector, then call recursive tour
   public  static void tour()
   {
      int[] vect = new int[n];
      int   start = Arrays.binarySearch(city, "Spokane");

      // First permutation n vector.
      for ( int k = 0; k < n; k++ )
         vect[k] = k;
      // We will, however, start from Spokane, not Coulee City
      // --- IF the data file is the one for the inland Pacific NW
      if ( start >= 0 )
      {  vect[start] = 0; vect[0] = start;  }
      tour(1, vect, 0);
   }

   // Used below in generating permutations.
   private static void swap ( int[] x, int p, int q )
   {  int tmp = x[p];  x[p] = x[q]; x[q] = tmp;  }

   // Recursive generation of the permutation vectors that constitute
   // possible paths.
   private static void tour(int index, int[] vect, int so_far)
   {
      if ( index == n )      // I.e., we have a full permutation vector
      {
         if ( wt[vect[n-1]][vect[0]] > 0 )  // IS there a return edge?
         {
            so_far = so_far + wt[vect[n-1]][vect[0]]; // Total tour distance
            if ( so_far < tourCost )        // Note initial flag value
            {
               System.arraycopy(vect, 0, solution, 0, n);
               tourCost = so_far;
               if ( DEBUG )
               {  System.out.print ("Accept "); partial ( vect, n );  }
            }
            else if (DEBUG)
            {  System.out.print ("Not shorter "); partial ( vect, n );  }
         }
         else if (DEBUG)
         {  System.out.print ("No return "); partial ( vect, n );  }
      }
      else                   // Continue generating permutations
      {
         int k;         // Loop variable
         int hold;      // Used in regenerating the original state

         for (k = index; k < n; k++)
         {
            int  testLength;

            swap (vect, index, k);
            if ( wt[vect[index-1]][vect[index]] > 0 )
            {  int increment = 0, j;

               for (j = index+1; j < n; j++)
                  increment += minAdditionalCost[vect[j]];
               testLength = so_far + wt[vect[index-1]][vect[index]];
               if (testLength+increment < tourCost)
                  tour (index+1, vect, testLength);
               else if (DEBUG)
                  System.out.printf("Cut at %d\n", index);
            }
         }
         // Regenerate the permutation vector
         hold = vect[index];
         for ( k = index+1; k < n; k++ )
            vect[k-1] = vect[k];
         vect[n-1] = hold;
      }
   }

   public static void main (String[] args) throws Exception
   {
      String filename = args.length == 0 ? "RoadSet.txt"
                                         : args[0];
      Scanner inp = new Scanner ( new java.io.File(filename) );
      long    start;

      System.out.println("Data read from file " + filename);
      init(inp);
      start = System.nanoTime();
      for (int pass = 0; pass < 100000; pass++)
      {
         tourCost = Integer.MAX_VALUE;
         tour();
         if (DEBUG) break;
      }
      System.out.printf ("Total time:  %3.3f milliseconds\n",
         1.0E-06 * (System.nanoTime() - start) );

      if ( tourCost < Integer.MAX_VALUE )
      {  System.out.printf("Best tour (length %d):  ", tourCost);
         partial ( solution, n );
      }
      else
         System.out.println("NO tours discovered.  Exiting.");
   }
}