#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <cassert>
#include <strings.h>

using namespace std;

string enstring(int n)
{ string s(1, '0' + n % 10);
  if (n < 10)
    return s;
  return enstring(n / 10) + s; }

string enstring(double num)
{ if (num == INFINITY)
    return "inf";
  return enstring((int) lround(num)); }

string enstring(double n, int width, bool addpointy = false)
{ string s = enstring(n);
  if (addpointy)
    s = string(1, '<') + s + '>';
  else
    s = s + ' ';
  int len = s.length();
  if (len < width)
    s = string(width - len, ' ') + s;
  return s; }

template <typename T> struct matrix
{ int size;
  T * data;

  matrix(initializer_list<initializer_list<T>> init)
  { size = init.size();
    data = new T[size * size];
    int row = 0;
    for (typename initializer_list<initializer_list<T>>::iterator row_it = init.begin(); row_it != init.end(); ++ row_it)
    { const initializer_list<T> & this_row = * row_it;
      assert(this_row.size() == size);
      int column = 0;
      for (typename initializer_list<T>::iterator col_it = this_row.begin(); col_it != this_row.end(); ++ col_it)
      { at(row, column) = * col_it;
        column += 1; }
      row += 1; } }

  matrix(int sz)
  { size = sz;
    data = new T[size * size];
    bzero(data, size * size * sizeof(T)); }

  ~matrix()
  { delete [] data; }

  int get_size()
  { return size; }

  T & at(int row, int column)
  { assert(row >= 0 && column >= 0 && row < size && column < size);
    return data[row * size + column]; }

  void print(int width, int from = -1, int dest = -1, int via = -1)
  { for (int row = 0; row < size; row += 1)
    { cout << "          ";
      for (int column = 0; column < size; column += 1)
        if (row == from && column == dest ||
            row == from && column == via ||
            row == via && column == dest)
          cout << enstring(at(row, column), width, true);
        else
          cout << setw(width - 1) << at(row, column) << ' ';
      cout << "\n"; } } };

const double inf = INFINITY;

int main()
{ string unused;
  matrix<double> * D0 = new matrix<double>({ {  0.0,  2.0,  2.0,  inf,  inf },
                                             {  2.0,  0.0,  5.0,  9.0,  4.0 },
                                             {  2.0,  5.0,  0.0, 17.0,  inf },
                                             {  inf,  9.0, 17.0,  0.0,  3.0 },
                                             {  inf,  4.0,  inf,  3.0,  0.0 } });
  int N = D0->get_size();
  for (int step = 0; step < N; step += 1)
  { 
    matrix<double> * D1 = new matrix<double>(N);
    cout << "D" << step << " is\n";
    D0->print(7);
    cout << "\n\n  creating D" << step + 1 << " from D" << step << ":\n\n";

    for (int row = 0; row < N; row += 1)

      for (int column = 0; column < N; column += 1)
      { cout << "    calculating D" << step + 1 << "[" << row << ", " << column << "], travel from " << row << " to " << column << " via anywhere <= " << step << ":\n";
        cout << "      choices are " << D0->at(row, column) << " or " << D0->at(row, step) << " + " << D0->at(step, column) << "\n\n";
        D0->print(7, row, column, step);

        D1->at(row, column) = min(D0->at(row, column), D0->at(row, step) + D0->at(step, column));

        cout << "\n    gives\n\n";
        D1->print(7, row, column);
        cout << "\n\n";
        getline(cin, unused); }

     cout << "D" << step << " was\n";
     D0->print(7);
     delete D0;
     D0 = D1; }

  cout << "\n\nfinal all shortest distances matrix:\n\n";
  D0->print(7);
  cout << "\n"; }