// Copyright Petri Kuukkanen joulukuu 2006

#include <iostream>
#include <vector>
#include <cmath>

struct Crossing
{
  float x, y;  // risteyksen koordinaatit
};

struct Road
{
  unsigned int begin, end; // risteykset, joiden välillä tie kulkee
  float length;            // tien pituus
};

std::vector<Crossing> crossings; // kaupungin kaikki risteykset
std::vector<Road> roads;         // kaupungin kaikki tiet

// Lisää tietorakenteeseen uusi risteys.
void addCrossing(float x, float y)
{
  Crossing c;
  c.x = x;
  c.y = y;
  crossings.push_back(c);
}

// Lisää tietorakenteeseen uusi tie.
void addRoad(unsigned int begin, unsigned int end, float length)
{
  Road r;
  r.begin  = begin;
  r.end    = end;
  r.length = length;
  roads.push_back(r);
}

// Palauta kahden risteyksen välinen linnuntietä pitkin mitattu etäisyys.
float crossingsDistance(unsigned int c1, unsigned int c2)
{
  float x1, y1, x2, y2;
  x1 = crossings[c1].x;
  y1 = crossings[c1].y;
  x2 = crossings[c2].x;
  y2 = crossings[c2].y;
  return sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
}

// Etsi parhaat risteyksestä c alkavat reitit syvyyteen ensin -haulla.
// Tämä on rekursiivinen (eli itseään kutsuva) funktio, jota kutsutaan
// funktiosta findBestRoute.
void findRoutes(unsigned int c, float l, int *R, float *L)
{
  unsigned int e, r;
  float f;
  for(r = 0; r < roads.size(); r++)
  {
    if(roads[r].begin != c) continue;
    e = roads[r].end;
    f = l + roads[r].length;
    if((R[e] == -1) || (L[e] > f))
    {
      R[e] = r;
      L[e] = f;
      findRoutes(e, f, R, L);
    }
  }
}

// Etsi paras reitti c:stä d:hen ja palauta reitin ensimmäisen tien numero.
int findBestRoute(unsigned int c, unsigned int d)
{
  if(c == d) return -1;
  unsigned int i, j, k, N = crossings.size();
  int   *R = new   int[N];
  float *L = new float[N];
  for(i = 0; i < N; i++) R[i] = -1;
  findRoutes(c, 0, R, L);
  j = R[d];
  if(j != -1) while((k = roads[j].begin) != c) j = R[k];
  delete[] R;
  delete[] L;
  return j;
}

int main()
{
  int i, j, k, N;

  // Tee muutamia risteyksiä.
  for(i = 0; i < 3; i++) for(j = 0; j < 3; j++) addCrossing(i, j);
  N = crossings.size();  // Vector-luokan size-metodi palauttaa vektoriin
                         // tallennettujen juttujen lukumäärän.

  // Tee N kappaletta satunnaisia teitä.
  for(i = 0; i < N; i++)
  {
    j = rand() % N;
    k = rand() % N;
    addRoad(j, k, crossingsDistance(j, k));  // menomatka j:stä k:hon
    addRoad(k, j, crossingsDistance(k, j));  // paluumatka k:sta j:hin
  }

  // Näytä parhaat reitit.
  for(i = 0; i < N; i++) for(j = 0; j < N; j++)
  {
    k = findBestRoute(i, j);
    if(k != -1)
    {
      cout << i << " -> " << j;
      cout << ": tie " << k << std::endl;
    }
  }

  return 0;
}