/* dijkstra1.c --- ダイクストラ法第１ステップ */
#include <stdio.h>
#include <math.h>
#include <string.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)
{
 // いままでとかわりません。
}

/* サーチとソートの演習のprint_crossを改変，距離を表示できるよう改造してます */
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);      /* 関数print_crossをnum回呼び出す */
}


int search_cross(int num)
{
/* サーチとソートで作成した search_cross をそのまま拝借 */

  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 done[CrossingNumber];     /* 確定済み:1 未確定:0 を入れるフラグ */
  力試しに、全部やってみてください。cross[i].distance が全部
  最短距離で埋まるように。できなさそうな場合 ↓に ある程度完成した
  関数をおいておきますので、それを参考に。
  時間はありますので、可能な限り、自分の頭で考えてみてください。
}

int main(void)
{
  int crossing_number;                          /* 交差点数 */
  int goal;
  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);

  return 0;
}