#include <stdio.h>
#include <stdlib.h>
#define K 4                     /* 基幹駅の数 */

typedef struct {
  char sec;
  int kl;
  int tokl;
  int kh;
  int tokh;
} STATION_INFO;

void calcDist(int n, int (*dist)[n]);
void print(int n, int (*dist)[n]);
int findMin(int d1, int d2, int d3, int d4);
int findShortestPath(int i, int j, int n, int (*dist)[n], STATION_INFO *si);

/* Warshall-Floyd法 */
void calcDist(int n, int (*dist)[n]) {
  int from, to, via;
#ifdef DEBUG
  print(n, dist);
#endif
  for (via = 0; via < n; via++) {
    for (from = 0; from < n; from++) {
      for (to = from + 1; to < n; to++) {
        if (dist[from][to] > dist[from][via] + dist[via][to]) {
          dist[from][to] = dist[from][via] + dist[via][to];
          dist[to][from] = dist[from][via] + dist[via][to];
        }
      }
    }
  }
#ifdef DEBUG
  print(n, dist);
#endif
}

void print(int n, int (*dist)[n]) {
  int from, to;
  for (from = 0; from < n; from++) {
    for (to = 0; to < n; to++) {
      printf("%4d", dist[from][to]);
    }
    printf("\n");
  }
  printf("\n");
}

int findMin(int d1, int d2, int d3, int d4) {
  int ret = d1;
  if (ret > d2) ret = d2;
  if (ret > d3) ret = d3;
  if (ret > d4) ret = d4;
  return ret;
}

int findShortestPath(int i, int j, int n, int (*dist)[n], STATION_INFO *si) {
  int d0, d1, d2, d3, d4, res;
  d1 = si[i].tokl + dist[si[i].kl][si[j].kl] + si[j].tokl;
  d2 = si[i].tokl + dist[si[i].kl][si[j].kh] + si[j].tokh;
  d3 = si[i].tokh + dist[si[i].kh][si[j].kl] + si[j].tokl;
  d4 = si[i].tokh + dist[si[i].kh][si[j].kh] + si[j].tokh;
  res = findMin(d4, d3, d2, d1);
  if (si[i].sec == si[j].sec) {
    d0 = abs(si[i].tokl - si[j].tokl); /* 同区間での距離 */
    if (d0 < res) res = d0;
  }
  return res;
}

int main(void) {
  /* 基幹駅の路線情報 */
  int dist[][K] = {{  0,  20,  40, 999},
                   { 20,   0,  15,  15},
                   { 40,  15,   0, 999},
                   {999,  15, 999,  0}};
  /* 駅情報表 */
  STATION_INFO si[10] = {{'0',  0,  0,  0,  0},  // 駅1
                         {'1',  1,  0,  1,  0},  // 駅2
                         {'2',  2,  0,  2,  0},  // 駅3
                         {'3',  3,  0,  3,  0},  // 駅4
                         {'B',  0, 15,  2, 30},  // 駅5
                         {'B',  0, 25,  2, 20},  // 駅6
                         {'C',  0,  5,  2, 35},  // 駅7
                         {'C',  0, 10,  2, 30},  // 駅8
                         {'C',  0, 30,  2, 10},  // 駅9
                         {'E',  1,  5,  3, 10}}; // 駅10
  int start, stop;
  calcDist(K, dist);
  printf("区間を指定 => "); scanf("%d %d", &start, &stop);
  printf("最短距離 = %d\n", findShortestPath(start - 1, stop - 1, K, dist, si));
  return 0;
}