#include <stdio.h>
#include <stdbool.h>

#define N (7) /* 地点の数 */

/* 地点間距離 */
/* ※1 地点aと地点bが同一の地点の場合は0が格納されている */
/* ※2 地点aと地点bが隣接地点でない場合は-1が格納されている */
/*static*/ int DISTANCE_MAP[N][N] = {
    /*a ->b 0   1   2   3   4   5   6 */
    /*0*/ {+0, +2, +8, +4, -1, -1, -1},
    /*1*/ {+2, +0, -1, -1, +3, -1, -1},
    /*2*/ {+8, -1, +0, -1, +2, +3, -1},
    /*3*/ {+4, -1, -1, +0, -1, +8, -1},
    /*4*/ {-1, +3, +2, -1, +0, -1, +9},
    /*5*/ {-1, -1, +3, +8, -1, +0, +3},
    /*6*/ {-1, -1, -1, -1, +9, +3, +0},
};

typedef const char *String;
typedef int Point;
typedef int Distance;
#define Distance_MAX (99999)

typedef struct route
{
  Point start, destination;
  Distance distance;
  Point point[N];
} Route;

void find_shortest(Route *route)
{
  Point point;
  Distance distance, shortest_distance[N];
  bool fixed[N];

  /* 初期化 */
  for (point = 0; point < N; point++)
  {
    shortest_distance[point] = Distance_MAX;
    fixed[point] = false;
  }
  shortest_distance[route->start] = 0;

  while (true)
  {
    /* 未確定地点を1つ探す */
    for (point = 0; point < N && fixed[point]; point++)
    {
    }
    if (point == N)
      return;

    /* 最短距離がより短い地点を探す */
    for (int i = point + 1; i < N; i++)
    {
      if (!fixed[i] && shortest_distance[i] < shortest_distance[point])
      {
        point = i;
      }
    }
    fixed[point] = true;

    /* 距離再計算 */
    for (int i = 0; i < N; i++)
    {
      if (fixed[i])
      {
        continue;
      }
      distance = DISTANCE_MAP[point][i];
      if (distance <= 0)
      {
        continue;
      }
      distance += shortest_distance[point];
      if (distance < shortest_distance[i])
      {
        shortest_distance[i] = distance;
        route->point[i] = point;
      }
    }
    route->distance = shortest_distance[route->destination];
  }
}

void print_route(Route *route, Point destination)
{
  /* 目的地から出発地までの経路を逆順にたどって出発地から表示する */
  if (route->start == destination)
  {
    printf("%d", route->start);
  }
  else
  {
    print_route(route, route->point[destination]);
    printf(" -> %d", destination);
  }
}

void print_shortest(Route *route)
{
  printf("出発地から目的地までの最短経路\n");
  print_route(route, route->destination);
  printf("\n出発地から目的地までの最短距離 = %d\n", route->distance);
}

void init_DISTANCE_MAP()
{
  int i, j;
  for (i = 0; i < N; i++)
  {
    for (j = 0; j < N; j++)
    {
      if (i == j)
      {
        DISTANCE_MAP[i][j] = 99999;
      }
    }
  }
}

Point input_point(String prompt)
{
  Point point;
  do
  {
    printf("%s", prompt);
    scanf("%d", &point);
  } while (point > N - 1);
  return point;
}

int main()
{
  Route route;
  init_DISTANCE_MAP();

  route.start = input_point("出発地の地点番号を入力してください ==> ");
  route.destination = input_point("目的地の地点番号を入力してください ==> ");
  find_shortest(&route);
  print_shortest(&route);

  return 0;
}