/* dijkstra2.c --- ダイクストラ法第２ステップ */
#include <stdio.h>
#include <string.h>
#include <math.h>

#define CrossingNumber 100  /* 交差点数=100 */
#define MaxName         50  /* 最大文字数50文字(半角) */

typedef struct {
  double x, y;             /* 位置 x, y */
} Position;                /* 位置を表す構造体 */

typedef struct {
  int id;                /* 交差点番号 */
  Position pos;          /* 位置を表す構造体 */
  double wait;           /* 平均待ち時間 */
  char jname[MaxName];   /* 交差点名 */
  char ename[MaxName];   /* 交差点名 */
  int points;            /* 交差道路数 */
  int next[5];           /* 隣接する交差点番号 */
  double distance;          /* 基準交差点からのトータル距離：追加 */
  int previous;          /* 基準交差点からの経路（直前の交差点番号）：追加 */
} Crossing;

Crossing cross[CrossingNumber];

int map_read(char *filename)
{
  FILE *fp;
  int i, j;
  int crossing_number;                          /* 交差点数 */

  fp = fopen(filename, "r");
  if (fp == NULL) {
    printf("File %s is not created\n", filename);
    return 0;
  }

  /* はじめに交差点数を読み込む */
  fscanf(fp, "%d", &crossing_number);
  if((crossing_number<1)||
     (crossing_number>=CrossingNumber))
    {
      printf("Illegal data number (%d)\n", crossing_number);
      return 0;
    }
  
  for (i = 0; i < crossing_number; i++) { 
    fscanf(fp, "%d,%lf,%lf,%lf,%[^,],%[^,],%d",
	   &(cross[i].id), &(cross[i].pos.x), &(cross[i].pos.y),
	   &(cross[i].wait), cross[i].jname, cross[i].ename, 
	   &(cross[i].points));

    for(j=0; j<cross[i].points; j++)
      fscanf(fp, ",%d", &(cross[i].next[j]));

  }
  fclose(fp);

  /* ファイルから読み込んだ交差点数を返す */
  return crossing_number;
}

/* 距離を表示できるよう改造してます */
void print_cross(int i)
{
  int j;
  printf("交差点番号:%2d, 座標(%5.2lf,%5.2lf), 名前: %s ( %s ),",
	 cross[i].id, cross[i].pos.x, cross[i].pos.y,
	 cross[i].jname,cross[i].ename);
  
  printf("\n    目的地までの距離 %5.1lf, 直前の交差点 :%d, 待ち時間:%5.1lf, 隣接交差点 :%d個 ( ", 
	 cross[i].distance, cross[i].previous, cross[i].wait, cross[i].points);  /* ここを改造 */
  for(j=0; j<cross[i].points; j++)         /* 交差道路数だけ繰り返し */
    printf("%d ", cross[i].next[j]);
  
  printf(")\n\n");
}


void print_cross_list(int num)  /* num個表示 = 表示数制限可能 */
{
  int i;
  for(i=0;i<num;i++)
    print_cross(i);
}


/* search_cross をそのまま拝借 */
int search_cross(int num)
{
  int i;
  int f= -1;
  char input[200];
  printf("交差点名を入力してください(ローマ字) ->");
  scanf("%s",input);
  
  puts("");
  for(i=0;i<num;i++)
    {
      if(strcmp(cross[i].ename,input)==0)
        {
          print_cross(i);
          f=i;
        }
    }
  if(f<0)
    printf("%s はみつかりませんでした\n",input);

  return f;  /* 見つかっていたら、それを、なければ -1 を返します */
}

/* 交差点 a と b の間の「距離」を与える */
double distance(int a, int b)
{
  return hypot(cross[a].pos.x-cross[b].pos.x,
	       cross[a].pos.y-cross[b].pos.y);
}

void dijkstra(int crossing_number,int target)
{
  int i,j,n;
  double min_distance;
  double d;
  int min_cross = 0;
  int done[CrossingNumber];     /* 確定済み:1 未確定:0 を入れるフラグ */

  for(i=0;i<crossing_number;i++)/* 初期化 */
    {
      cross[i].distance=1e100;  /* 初期値は有り得ないくらい大きな値 */
      cross[i].previous=-1;     /* 最短経路情報を初期化 */
      done[i]=0;                /* 全交差点未確定 */
    }

  /* ただし、基準の交差点は 0 */
  cross[target].distance=0;
  
  for(i=0;i<crossing_number;i++) /* c_number回やれば終わるはず */
    {
      /* 最も距離数値の小さな未確定交差点を選定 → サーチのところ参照 */
      min_distance=1e100;
      for(j=0;j<crossing_number;j++)
	{  /* _未確定？_    ______暫定最短より近い？_______ */
	  if((done[j]==0)&&(cross[j].distance < min_distance))
	    {
	      min_distance=cross[j].distance;
	      min_cross=j;
	    }
	}
      /* 交差点 min_cross は 確定できる */
      done[min_cross]=1;  /* 確定 */
      /* 確定交差点周りで距離の計算 */
      for(j=0;j<cross[min_cross].points;j++)
	{
	  n=cross[min_cross].next[j];    /* 長ったらしいので置き換え(だけ) */
	  /* 評価指標 */
	  d=distance(min_cross,n)+cross[min_cross].distance;
	  /* 現在の暫定値と比較して、短いなら更新 */
	  if(cross[n].distance > d)
	  {
	    cross[n].distance = d;
	    cross[n].previous = min_cross;
	  }
	}
    }
}

/* 最短パス設定 */
int pickup_path(int crossing_number,int start,int goal,
		int path[],int maxpath)
{
  int c=start;         /* 現在いる交差点 */
  int i;

  path[0]=start;
  i=1;
  c=start;             /* 現在値を start に設定 */
  while(c!=goal)
    {
      c=cross[c].previous;
      path[i]=c;
      i++;
    }
  path[i]=-1;   /* おしまいのマーク */
  return 0;
}

int main(void)
{
  int crossing_number;                          /* 交差点数 */
  int goal,start;
  int path[20];
  int i;

  /* ファイルの読み込み */
  crossing_number = map_read("map2.dat");
  printf("loaded %d crossings\n",crossing_number);
  for(i=0;i<crossing_number;i++)
    {
      cross[i].distance=0;    /* 適当に初期化しておきます for print_cross */
      cross[i].previous=-1;    /* 適当に初期化しておきます for print_cross */
    }

  /* 目的地の取得 */
  printf("目的地を決定します。");
  goal=search_cross(crossing_number);

  if(goal<0)
    return 1;    /* 目的地決定失敗 */

  dijkstra(crossing_number,goal);
  print_cross_list(crossing_number);

  printf("現在地を決定します。");
  start=search_cross(crossing_number);
  if(start<0)
    return 1;

  if(pickup_path(crossing_number,start,goal,path,20)<0)
    return 1;

  printf("経路確定しました\n");
  i=0;
  while(path[i]>=0)
    {
      printf("%2d %5.1lf %s\n",
	     i+1,cross[path[i]].distance,cross[path[i]].jname);
      i++;
    }
  return 0;
}