import java.util.ArrayList;

/**
     Instances of this class are immutable objects representing
       weighted directed graphs (with no loops or multiple edges).
     Vertices are represented by <code>int</code>s, as are edge weights.
     Infinite edge weights are represented by the value Integer.MAX_VALUE.
     The methods of this class are not guaranteed to work correctly
       if the absolute values of path costs exceed this value, or
       if the matrices fail to satisfy the constraints required for
       correct behavior of the underlying algorithm.
 */

public class Graph
{
    private int n;                 // the number of vertices
    private int[][] adjacency;     // the (weighted) adjacency matrix

    
    /**
        This constructor builds a graph with a given adjacency matrix,
          except that (1) entries on the main diagonal are required to be 0
          (2)  rows with more elements than there are rows are truncated,
          and (3) rows with fewer elements than there are rows are padded
          with trailing zeros.         
     */
    
    public Graph(int[][] array)                               {
      n = array.length;
      adjacency = new int[n][n];
        for (int i=0; i<array.length; i++)                  {
          for (int j=0; j<Math.min(n,array[i].length); j++)
            adjacency[i][j] = array[i][j];                   
          adjacency[i][i] = 0;                              } }

  
    /** 
         This constructor builds a complete graph of 8 vertices
         where all edge costs are 0.
     */
    public Graph()                                            {
      this(new int[8][8]);                                    }
      
      
    /**
         Constructs a graph of a given number of vertices with 
           no adjacency matrix.  Private methods may then 
           assign an adjacency matrix which does not have 
           zeros down the main diagonal
     */  
    
    private Graph(int n)                                      {
      this.n = n;                                             }
      
      
    /**
         Builds a graph with a given adjacency matrix,
           which is assumed to be square and not to need cloning.
    */
   
    private Graph buildGraph(int[][] array)                   {
      Graph g = new Graph(array.length);
      g.adjacency = array;                                
      return g;                                               }
        
      
  ///////////////////// PUBLIC METHODS ////////////////////////////
  
  /**
      Finds the cost of the cheapest path between every
        pair of vertices, using the strategy of the algorithm 
        of Section 7.2 of the Goodrich & Tamassia text, but
        using the analog of ordinary matrix multiplication
        to construct the intermediate matrices.
      @return a graph whose edge costs represent the cost
        of the cheapest path from one endpoint to the other.
   */
  
    public Graph naiveAllPairs()                                  {
      int[][] returnMatrix = new int[n][n];
      for (int i=0; i<n; i++)
        for (int j=0; j<n; j++)
          returnMatrix[i][j] = adjacency[i][j];  
      for (int i=1; i<n; i++)                                
        returnMatrix = gtProduct(returnMatrix, adjacency);
      return buildGraph(returnMatrix);                            }
      
      
  /**
      Finds the cost of the cheapest path between every
        pair of vertices, using the Floyd-Warshall algorithm.
      @return a graph whose edge costs represent the cost
        of the cheapest path from one endpoint to the other.
   */
  
     public Graph floydAllPairs()                                 {
      Graph g = this;  
      for (int i=0; i<n; i++)                               
        g = g.floydProduct(g, i);
      return g;                                                   }     
      
      
  /**
      Finds the cost of the cheapest path between every
        pair of vertices, using the algorithm of Section 7.2
        of the Goodrich & Tamassia text.
      @return a graph whose edge costs represent the cost
        of the cheapest path from one endpoint to the other.
   */
        
    public Graph gtAllPairs()                                     {  
      Graph paddedGraph = this.pad();   
      int[][] returnMatrix =  
         findClosure(paddedGraph.adjacency);  
      Graph returnGraph = buildGraph(returnMatrix);
      returnGraph.n = n;       // unpad
      return returnGraph;                                         }  

      
    /**
        Finds the cost of the cheapest path between every
          pair of vertices, using the Bellman-Ford algorithm 
          once for each vertex in the graph.  There is no indication
          returned of whether there is a negative cost cycle.
       @return a graph whose edge costs represent the cost
         of the cheapest path from one endpoint to the other.
    */

    public Graph bfAllPairs()                                    {
      int[][] adjacency = new int[n][n];
      for (int i=0; i<n; i++)
        adjacency[i] = bellmanFord(i);
      return buildGraph(adjacency);                              }

      
    /**
        Finds the cheapest path from a given 
          vertex to another given vertex, using the Bellman-Ford 
          algorithm.  If there is a negative cost cycle present
          in the graph, the path returned will be unreliable,
          since no cheapest path can exist.
       @param source the first vertex   
       @param dest the second vertex
       @return the cheapest path, represented as an array of
         vertex numbers including the source and destination vertex.
    */

    public int[] bfSinglePair(int source, int dest)              {
      ArrayList<Integer> reversedPath = 
        bellmanFordWithDestination(source, dest);
      int[] path = new int[reversedPath.size()];
      int index = path.length - 1;
      for (Integer i : reversedPath)                    {
        path[index] = i;
        index--;                                        }
      return path;                                                }


    /**
        Constructs a string representing the (weighted) adjacency matrix
           of the graph, as a 2-dimensional table.
        Infinite values are represented as asterisks
        @return the string   
     */  
    // Note the use of System.getProperty("line.separator")
    //   for platform independence.
    
    public String toString()                                      {
      StringBuffer sb = new StringBuffer();  
      for (int i=0; i<n; i++)                               {
        for (int j=0; j<n; j++)                        
          if (adjacency[i][j] == Integer.MAX_VALUE)
            sb.append("     *");
          else
            sb.append(String.format("%6d", adjacency[i][j]));  
        sb.append(System.getProperty("line.separator"));    }
      return new String(sb);                                      }  
      
  
   /**
        Determines whether the graph is to another graph
          by checking their adjacency matrices for pointwise
          equality -- no check is made for isomorphism.
        @param o the other graph  
        @throws ClassCastException if the parameter is not a graph
   */

   public boolean equals(Object o)                                {
     Graph g = (Graph) o;
     if (n != g.n)
       return false;
     for (int i=0; i<n; i++)                               
       for (int j=0; j<n; j++)                        
         if (adjacency[i][j] != g.adjacency[i][j])
           return false;
     return true;                                                 } 


   /**
       @return the number of vertices in the graph
   */
          
   public int getSize()                                {
     return n;                                         }

    
  //////////// PRIVATE METHODS FOR FLOYD-WARSHALL ALL-PAIRS ////////

    /**
        Constructs a graph whose edge cost for a vertex pair (i,j)
          represents the cost of the cheapest path from i to j
          whose only allowable intermediate vertex is l.  
        This method can be thought of as a variant of matrix 
          multiplication.  It is associative but not commutative.
        If the graphs have different sizes, returns the graph
          of smaller size obtained by ignoring entries of the
          larger graph with an index larger than this size
        @param g the given graph
        @param l the number of the allowable intermediate vertex
        @return the new graph 
     */

        
    private Graph floydProduct(Graph g, int l)                    {
        int size = Math.min(n, g.n);
        int[][] returnArray = new int[size][size];
        for (int i=0; i<size; i++)        
          for (int j=0; j<size; j++)                          
            returnArray[i][j] = 
              minWithOverflow(adjacency[i][j],
                      adjacency[i][l], g.adjacency[l][j]);     
        return buildGraph(returnArray);                           }


  //////// PRIVATE METHODS FOR GOODRICH-TAMASSIA ALL-PAIRS ///////

   /*  
       None of these methods checks that their input is of the proper
         size, since all are private.
       Most of them take arrays as arguments to minimize the copying
         that is done by the Graph constructor, and because the
         Graph constructor that takes an adjacency matrix
         adds zero entries down the main diagonal
  */             

  
  /**      
       This method finds the closure (the cost of the cheapest path between
         every pair of vertices) for a graph.
       It is not guaranteed to work correctly if there are negative-cost
          cycles
       @param adj the adjacency matrix for the graph whose
         closure is to be found.  Note that these matrices
         need not have zeros on the main diagonal when
         passed recursively.
       @return the adjacency matrix for the closure
  */
  /*
    This method uses the recursive algorithm on pages 358-9 of the
      Goodrich & Tamassia text.  It could perhaps be implemented more efficiently
      if it passed array indices rather than the arrays themselves.
    The recursion could terminate at n=2, at least if zeros are to appear
      on the main diagonal
  */

    private static int[][] findClosure(int[][] adj)                {
      int n = adj.length;
      int halfN = n/2;  
      if (n == 1)                        {
        return adj;                      }

      // split the input array into 4 equal size pieces
      int[][] b = new int[halfN][halfN];        
      int[][] c = new int[halfN][halfN];        
      int[][] d = new int[halfN][halfN]; 
      int[][] e = new int[halfN][halfN];        
      for (int i=0; i<halfN; i++)                    {
        for (int j=0; j<halfN; j++)
          b[i][j] = adj[i][j];
        for (int j=halfN; j<n; j++)
          c[i][j-halfN] = adj[i][j];      }
      for (int i=halfN; i<n; i++)                    {
        for (int j=0; j<halfN; j++)
          d[i-halfN][j] = adj[i][j];
        for (int j=halfN; j<n; j++)
          e[i-halfN][j-halfN] = adj[i][j];  }
        int[][] eStar = findClosure(e);
      int[][] w = 
        findClosure(gtMin(b,
                      gtProduct(c,
                        gtProduct(eStar, d))));                      
      int[][] x = gtProduct(w, 
                     gtProduct(c, eStar));        
      int[][] y = gtProduct(eStar, 
                     gtProduct(d, w));        
      int[][] z = gtMin(eStar, 
                   gtProduct(eStar, 
                     gtProduct(d, 
                       gtProduct(w, 
                         gtProduct(c, eStar)))));        
      return combine(w,x,y,z);                                  }
      

    /**
         Pad the graph by rounding its size up to the next power of 2,
           and adding new entries that are infinite off the main diagonal
           and 0 on it.  This method does not modify the graph.
         @return the new, padded graph
    */
    // Note that the new zero entries are added by the Graph constructor
 
    private Graph pad()                                           {    
      int originalSize = n;
      int n = 1;             // ok to shadow instance field
      while (n < originalSize)                               {
        n = n + n;                                           }
      int[][] returnArray = new int[n][n];
      for (int i=0; i<originalSize; i++)         {
        for (int j=0; j<originalSize; j++)
          returnArray[i][j] = adjacency[i][j];          
        for (int j=originalSize; j<n; j++)
          returnArray[i][j] = Integer.MAX_VALUE; }
      for (int i=originalSize; i<n; i++)
        for (int j=0; j<n; j++)
          returnArray[i][j] = Integer.MAX_VALUE;            
      return buildGraph(returnArray);                             }
          

    /**
         Builds a 2m by 2m array out of four m by m arrays,
           with one input array in each corner.
         None of the four arrays are modified or cloned
           by this method.
         @param w the array for the upper-left corner
         @param x the array for the upper-right corner
         @param y the array for the lower-left corner
         @param z the array for the lower-right corner
     */  
    
    private static int[][] combine(int[][] w, int[][] x, 
                              int[][] y, int[][] z)                  {
      int n = w.length;
      int[][] returnArray = new int[2*n][2*n];
      for (int i=0; i<n; i++)                     {
        for (int j=0; j<n; j++)
          returnArray[i][j] = w[i][j];
       for (int j=n; j<2*n; j++)
          returnArray[i][j] = x[i][j-n];          }
      for (int i=n; i<2*n; i++)                   {
        for (int j=0; j<n; j++)
          returnArray[i][j] = y[i-n][j];
        for (int j=n; j<2*n; j++)
          returnArray[i][j] = z[i-n][j-n];        }
      return returnArray;                                            }
      
      
     /**
        Constructs an adjacency matrix whose edge costs are the 
          pointwise minima of those of two given matrices.
        If the matrices have different sizes, returns the matrix
          of smaller size obtained by ignoring entries of the
          larger one with an index larger than this size
        @param g1 the first matrix
        @param g2 the second matrix
        @return the desired matrix 
     */
     
    private static int[][] gtMin(int[][] g1, int[][] g2)      {
        int size = g1.length;
        int[][] returnArray = new int[size][size];
        for (int i=0; i<size; i++)
          for (int j=0; j<size; j++)
            returnArray[i][j] = 
              Math.min(g1[i][j], g2[i][j]);
        return returnArray;                                   }
        
      
  //////// PRIVATE METHODS FOR THE BELLMAN-FORD ALL-PAIRS ALGORITHMS ///////

   /*
       These methods could be augmented with a test for whether the
         graph contains a negative-cost cycle.
       Also note that they use an adjacency matrix, so they will 
         have cubic time complexity even for sparse graphs.
   */


   /**
        For graphs with no negative-cost cycle, finds the cheapest path 
          to every vertex in the graph from a given source vertex
        @param source the source vertex
        @return an array whose ith entry is the cost of the cheapest
          path to vertex i, if there is no negative-cost cycle.
    */

   private int[] bellmanFord(int source)              {
     int[] d = new int[n];
     for (int i=0; i<n; i++)
       d[i] = Integer.MAX_VALUE;
     d[source] = 0;
     for (int i=1; i<n; i++)
       for (int u=0; u<n; u++)
         for (int z=0; z<n; z++)                        {
           int min = minWithOverflow(
                        d[z], d[u], adjacency[u][z]);     
             d[z] = min;                                }
       return d;                                               }
      

   /**
        Finds the cheapest path between two vertices,
          using the Bellman-Ford algorithm
        @param source the source vertex
        @param dest the destination vertex
        @return a sequence of integers representing
          the vertices on the path, including the
          source and destination vertex.
    */

   private ArrayList<Integer> bellmanFordWithDestination(
     int source, int dest)                                     {
     final int ILLEGAL_VERTEX = -1;    
     int[] d = new int[n];
     int[] pred = new int[n];   // the predecessor vertices
     for (int i=0; i<n; i++)                            {
       d[i] = Integer.MAX_VALUE;
       pred[i] = ILLEGAL_VERTEX;                        }
     d[source] = 0;
     for (int i=0; i<n; i++)
       for (int u=0; u<n; u++)
         for (int z=0; z<n; z++)                        {
           int min = minWithOverflow(
                        d[z], d[u], adjacency[u][z]);     
             if (d[z] != min)
               pred[z] = u;
             d[z] = min;                                }

     // now extract the path from the "pred" matrix
     ArrayList<Integer> path = new ArrayList<Integer>();
     int v = dest;
     while (v != ILLEGAL_VERTEX)                        {
       path.add(v);
       v = pred[v];                                     }
     return path;                                               }
      
       
  //////// PRIVATE METHODS FOR MULTIPLE ALL-PAIRS ALGORITHMS ///////

     /**
        Constructs an adjacency matrix for a graph whose edge cost 
          for a vertex pair (i,j) represents the cost of a cheapest 
          path of length at most r+s between i and j, given a graph 
          that does the same for paths of length r and a graph that
          does the same for paths of length s.
        This method can be thought of as a variant of matrix 
          multiplication.  It is associative but not commutative.
        @param g the given graph
        @return the new graph 
     */
     
    private static int[][] gtProduct(int[][] adj1, int[][] adj2)    {
        int size = adj1.length;
        int[][] returnArray = new int[size][size];
        for (int i=0; i<size; i++)
          for (int j=0; j<size; j++)                          {
            int min =Integer.MAX_VALUE;   
            for (int l=0; l<size; l++)
              min = minWithOverflow(min,
                      adj1[i][l], adj2[l][j]);
            returnArray[i][j] = min;                          }          
        return returnArray;                                         }
        
        
    /**
         Finds the minimum of one integer and the sum of two 
           others, given that one or both of the last two
           integers may represent infinity.
         Assumes that the sum will not overflow.
         @param m the first integer
         @param r the first summand
         @param s the second summand
         @return the minimum as described above
     */
    
    private static int minWithOverflow(int m, int r, int s)       {
      if (r == Integer.MAX_VALUE)  
        return m;
      if (s == Integer.MAX_VALUE)
        return m;
      else return Math.min(m, r+s);                               }
      
            
 
}