// ----------------------------------------------------------------------------
//
// All pairs shortes path problem.
// 
// In:  N x N matrix W such that
//       W(i,j) = weight of edge from i to j (or infinity, if none)
//
// Out: N x N matrix W such that
//      W(i,j) = length of shortest path from i to j (or infinity, if none)
//
// (c) Wolfgang Schreiner, 2005.
//
// ----------------------------------------------------------------------------

import java.util.*;

public class PathJ
{
  final static int N = 768;       // matrix dimension
  final static int L = 10;         // N = 2^L
  final static int D = 1;         // matrix density in percent
  final static int MAX = 100;     // maximum edge weight
  final static int INF = N*MAX+1; // infinity, N*MAX < INF, 2*INF must be in range

  // print result flag
  final static boolean flag = false;  

  // ----------------------------------------------------------------------------
  //
  // initialize W
  //
  // ----------------------------------------------------------------------------
  private static void init(float[][] W) 
  {
    Random r = new Random(3142);

    for (int i = 0; i < N; i++)       /* initialize by random numbers */
    {        
      for (int j = 0; j < N; j++) 
      {
	if (r.nextInt(100/D) == 0)
	  W[i][j] = r.nextInt(MAX);   /* weight of edge between i and j */
	else
	  W[i][j] = INF;              /* no edge between i and j */
      }
    }
    for (int i = 0; i < N; i++)       /* initialize diagonale */
      W[i][i] = 0;

  }

  // ----------------------------------------------------------------------------
  // 
  // print W
  // 
  // ----------------------------------------------------------------------------
  private static void print(float[][] W) 
  {
    int n = 0;
    for (int i = 0; i < N; i++) 
    {
      for (int j = 0; j < N; j++) 
      {
	if (W[i][j] == INF) 
	{
	  if (flag) System.out.print(" ");
	}
	else 
	{
	  n++;
	  if (flag) System.out.print(".");
	}
      }
      if (flag) System.out.println();
    }
    System.out.println("*** " + n + " paths ***");
  }

  // ----------------------------------------------------------------------------
  // 
  // square A to B
  // 
  // ----------------------------------------------------------------------------
  private static void square(float[][] A, float[][] B) 
  {
    for (int i = 0; i < N; i++) 
    {
      for (int j = 0; j < N; j++) 
      {
	float m = A[i][j];
	for (int k = 0; k < N; k++) 
	  m = Math.min(m, A[i][k] + A[k][j]);
	B[i][j] = m;
      }
    }
  }

  // ----------------------------------------------------------------------------
  // 
  // copy A to B
  // 
  // ----------------------------------------------------------------------------
  private static void copy(float[][] A, float[][] B) 
  {
    for (int i = 0; i < N; i++) 
      for (int j = 0; j < N; j++) 
	B[i][j] = A[i][j];            
  }

  // ----------------------------------------------------------------------------
  // 
  // compute all pairs shortest paths
  //
  // ----------------------------------------------------------------------------
  private static void path(float[][] W) 
  {
    float[][] V = new float[N][N];

    int t = 0;
    for (int s = 0; s < L-1 ; s++) {   
      if (t == 0)
	square(W, V);             /* V = W^2 */
      else
	square(V, W);             /* W = V^2 */
      t = 1 - t;
    }
    if (t == 1) copy(V, W);       /* W = V */
  }

  // ----------------------------------------------------------------------------
  //
  // main program
  //
  // ----------------------------------------------------------------------------
  public static void main(String[] args) 
  {
    float[][] W = new float[N][N];

    init(W);  /* initialize matrix */
    print(W); /* print input */
    path(W);  /* compute all shortest pathes */
    print(W); /* print result */
  }
}