// Klasse für kürzeste Wege zwischen Städten (Floyd-Warshall-Algorithmus)
//
// Aufruf: matrix
//
// Klaus Kusche, 2011

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <cmath>

using namespace std;

// Anzahl der Städte
const unsigned int ANZAHL = 9;

// Initialwerte für die Entfernungen
const double init[ANZAHL][ANZAHL] = {
  { },
  { 37 },
  { 24, 0 },
  { 40, 0, 0 },
  { 0, 0, 0, 47 },
  { 0, 0, 0, 0, 70 },
  { 45, 24, 60, 0, 0, 0 },
  { 67, 70, 95, 0, 0, 0, 43 },
  { 103, 0, 44, 104, 162, 0, 85, 85 }
};

// Städtenamen (Beschriftungen für die Ausgabe)
const char *beschr[ANZAHL] = {
  "Gera", "Greiz", "Zeitz", "Jena",
  "Erfurt", "Eisenach", "Zwickau", "Chemnitz", "Leipzig"
};

class Wege
{
  friend ostream &operator<<(ostream &outFile, const Wege &w);

  public:
  
    Wege(unsigned int anz, const char **n)
    : anzahl(anz), dist(new double *[anz]), optim(false), namen(n)
    {
      for (unsigned int von = 0; von < anz; ++von) {
        dist[von] = new double[anz];
        for (unsigned int nach = 0; nach < anz; ++nach) {
          dist[von][nach] = HUGE_VAL;
        }
      }
    }
    
    ~Wege() {
      for (unsigned int von = 0; von < anzahl; ++von) {
        delete [] dist[von];
      }
      delete [] dist;
    }
    
    unsigned int getAnz() const { return anzahl; }
    
    double get(unsigned int von, unsigned int nach) const {
      if ((von >= anzahl) || (nach >= anzahl)) {
        return HUGE_VAL;
      }
      return dist[von][nach];
    }
    
    bool set(unsigned int von, unsigned int nach, double d) {
      if (optim || (d < 0) || (von >= anzahl) || (nach >= anzahl)) {
        return false;
      }
      dist[von][nach] = d;
      return true;
    }

    void calc() {
      double d;
      
      optim = true;
      for (unsigned int ueber = 0; ueber < anzahl; ++ueber) {
        for (unsigned int von = 0; von < anzahl; ++von) {
          for (unsigned int nach = 0; nach < anzahl; ++nach) {
            d = dist[von][ueber] + dist[ueber][nach];
            if (d < dist[von][nach]) {
              dist[von][nach] = d;
            }
          }
        }
      }
    }
    
  private:
    Wege(const Wege &w);
    Wege &operator=(const Wege &w);
    
    unsigned int anzahl;
    double **dist;
    bool optim;
    const char **namen;
};

ostream &operator<<(ostream &outFile, const Wege &w)
{
  cout << setw(9) << ' ' << ' ';
  for (unsigned int nach = 0; nach < w.anzahl; ++nach) {
    cout << setw(9) << w.namen[nach] << ' ';
  }
  cout << endl;
  
  for (unsigned int von = 0; von < w.anzahl; ++von) {
    cout << setw(9) << left << w.namen[von] << right << ' ';
    for (unsigned int nach = 0; nach < w.anzahl; ++nach) {
      cout << fixed << setw(9) << setprecision(1) << w.dist[von][nach] << ' ';
    }
    cout << endl;
  }
  cout << endl;
  
  return outFile;
}

int main()
{
  Wege w(ANZAHL, beschr);
  
  for (unsigned int von = 0; von < ANZAHL; ++von) {
    w.set(von, von, 0);
    for (unsigned int nach = 0; nach < von; ++nach) {
      if (init[von][nach] > 0) {
        w.set(von, nach, init[von][nach]);
        w.set(nach, von, init[von][nach]);
      }
    }
  }

  cout << w;
  w.calc();
  cout << w;
  
  exit(EXIT_SUCCESS);
}