#if 0
初めて呼損が起こるまでに確率できた通信回数を評価したい。
次のプログラムに追加して、以下の方法で評価を行うプログラムを完成させてください。

1、ランダムに送受信ノードを決定する
2、与えられた送受信ノード間の経路を決定する
(a)その経路上の全てのリンクに空き容量がある場合、それらを1Mbpsだけ減少させ、
「確率できた通信回数」を1増やし、手続き1に戻る
(b)その経路上に空き容量のないリンクが存在する場合、呼損とし、その時点までの
「確率できた通信回数」を記録して手続き3に進む。
3、全リンクの空き容量を初期状態に戻し、手続き1に戻る
4、1～3の手続きを1000回行い、「初めて呼損が起こるまでに確立できた通信回数」の平均を算出する。
#endif

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define NODE_NUM 10 /* 総ノード数 */
#define MAX 9999 /* 無限大に相当する数 */

#define FLAG 1 /* Dijkstraのテストの場合は0に、シミュレーション評価を行う場合は1にする */

int main()
{
/* Dijkstraのアルゴリズム部分で必要な変数 */
  int graph[NODE_NUM][NODE_NUM]; /* 距離行列 */ 
  int path[NODE_NUM]; /* 前ノード表 */
  int dist[NODE_NUM]; /* 距離を格納 */
  int chk[NODE_NUM]; /* 最短距離確定のフラグ */
  int tmp_node, tmp_dist; /* 注目しているノードとそこまでの最短距離 */
  int src, dest; /* 始点・終点ノード */
  int a, b, c, d, i, j, min;
  int fin; /* 未確定ノードが残っているかどうかのフラグ */
  FILE *fp; /* 距離の入ったファイルを示すポインタ */

  /* シミュレーション評価の部分で必要な変数 */
  int link[NODE_NUM][NODE_NUM]; /* リンク容量 */
  int bandwidth[NODE_NUM][NODE_NUM]; /* リンクの空き容量 */
  int miss; /* 呼損を表すフラグ */
  int success; /* 確立できた通信回数 */
  int sum_success; /* 確立できた通信回数の合計 */
  int sim_time; /* 評価の回数をカウント */
  int tmp;

/*
距離行列の作成
 */
  for (i=0; i<NODE_NUM; i++){
    for (j=0; j<NODE_NUM; j++){
      graph[i][j] = MAX; /* 接続されていないノード間の距離をMAXにする */
      link[i][j] = -1; /* 接続されていないノード間のリンク容量を-1にする */
      if (i == j){ graph[i][j] = 0; link[i][j] = -1;}/* そのノード自身への距離は0とし、リンク容量は-1とする */
    }
  }
  fp=fopen("./distance.txt", "r");
  while(fscanf(fp, "%d %d %d %d", &a, &b, &c, &d) != EOF) { /* EOFまで4つ組を読み込む */
    graph[a][b]=c; /* 接続されているノード間の距離を設定 */
    graph[b][a]=c; /* 逆方向も等距離と仮定 */
    link[a][b]=d; /* 接続されているノード間のリンクを設定 */
    link[b][a]=d; /* 逆方向も同じ容量と仮定 */
  }
  fclose(fp);
/* 
始点・終点ノードを標準入力から得る (評価の場合は、実行しない)
*/
  if (FLAG == 0) {
    printf("Source Node?(0-%d)", NODE_NUM-1);
    fscanf(stdin, "%d", &src);
    printf("Destination Node?(0-%d)", NODE_NUM-1);
    fscanf(stdin, "%d", &dest);
  }

  if (FLAG == 1) srand((unsigned)time(NULL)); /* 乱数の初期化, これ以降、rand()で乱数を得ることができる */

/****************************/
/* シミュレーション評価開始 */
/****************************/

#define N 1000
  success = 0; sum_success = 0; /* 評価指標を初期化 */
  for (sim_time = 0; sim_time < N; sim_time++) {
    miss = 0; /* 空きリンクが存在しない場合のフラグをOFFにする */
    success = 0; /* 確立できた通信回数を初期化する */
    
    for (i=0; i<NODE_NUM; i++) { /* 全リンクの空き容量を初期状態に戻す */
      for (j=0; j<NODE_NUM; j++) {
        bandwidth[i][j] = link[i][j];
      }
    }

    while (miss == 0) { /* 呼損が発生するまで繰り返す */
      if (FLAG == 1) {
        /* 評価の場合、送受信ノードをランダムに決定 */
        src = rand() % NODE_NUM;
        dest = rand() % NODE_NUM;
        if (src == dest) {
/*          printf("送受信ノードが一致している\n"); */
          continue;
        }
        printf("%d: src=%d, dest=%d\n", sim_time, src, dest); /* 送受信ノードを表示 */
      }

      for (i = 0; i < NODE_NUM; i++) { /* 何も確定していない状態にする */
        dist[i] = MAX;
        chk[i] = 0;
        path[i] = NODE_NUM;
      }
      path[src] = src; /* 始点ノードへの経路上の前ノードはそれ自身とする */
      dist[src] = 0; /* 始点ノード自身への距離は0である */
      chk[src] = 1; /* 始点ノードへの最短距離は確定 */
      tmp_node = src; /* 始点ノードから探索を始める */
      fin = 0;

      /* 2. 送信ノードに接続されている全てのノードについて、接続リンクの長さを送信ノードからの長さとする */
      for (i = 0; i < NODE_NUM; i++) {
        if (graph[tmp_node][i] != MAX) {
          dist[i] = graph[tmp_node][i];
          path[i] = tmp_node;
        }
      }
      /* 3. 送信ノードに接続されている全てのノードうち、最短の距離をもつノードを確定とする */
      min = MAX, tmp_node = -1;
      for (i = 0; i < NODE_NUM; i++) {
        if (chk[i] != 1 && dist[i] < min) {
          min = dist[i];
          tmp_node = i;
        }
      }
      chk[tmp_node] = 1;
      path[tmp_node] = src;
    
      while (fin == 0) { /* finフラグが立つまで繰り返す */
        /* 4. 確定したノードに接続されている全てのノードについて、送信ノードからこの確定ノードを経由して到着する経路の距離を
        計算し、これまでの距離より短ければ更新する */
        
        /* 確定したノードに接続している全てのノードについて */      
        /* srcからtmp_nodeまでの距離とtmp_nodeから現在考えているノードiまでの距離を計算 */
        /* これまでの距離より短ければ */
        /* distとpathを更新する */
        for (i = 0; i < NODE_NUM; i++) {
          if (i == tmp_node)
            continue;
          if (chk[i] > 0)
            continue;
          if (dist[i] < dist[tmp_node] + graph[tmp_node][i]) {
            ;
          } else {
            dist[i] = dist[tmp_node] + graph[tmp_node][i];
            path[i] = tmp_node;
          }
        }
        /* 5. まだ確定していないノードのうち、送信ノードからの距離が最短のノードを確定とする*/
        min = MAX;
        for (i = 0; i < NODE_NUM; i++) {
          if (chk[i] == 0 && dist[i] < min) {
            min = dist[i];
            tmp_node = i;
          }
        }
        chk[tmp_node] = 1;
        if (chk[dest] == 1) fin = 1; /* 終点ノードへの最短距離が確定したら終了 */
      }
    
      /* 
      結果出力(Dijkstra作成時のみ実行する)
      */

      if (FLAG == 0) {
        if (dist[dest] >= MAX) {
          printf("No path from node%d to node%d.\n",src,dest);
        } else {
          printf("Shortest path from node%d to node%d is as follows.\n",src,dest);
          printf("%d <- ",dest);
          i = dest;
          for(i = path[i]; i != src; i = path[i]){/* 前ノード表を辿る */
            printf("%d <- ",i);
          }
          printf("%d\n",src);
          printf("Shortest distance is %d.\n", dist[dest]);
        }
        return 0; /* Dijkstraの作成時は結果を出力したらプログラムを終了する */
      }
      
      /************************************/
      /* ここまでがdijkstraのアルゴリズム */
      /************************************/

      /*      2-(a) その経路上の全てのリンクに空き容量がある場合、それらを1Mbpsだけ
      減少させ、「確立できた通信回数」を1増やす
       */
    
       for (i = dest; i != src; i = path[i]) {
        if ((tmp = --bandwidth[i][path[i]]) < 0)
          break;
        if ((tmp = --bandwidth[path[i]][i]) < 0)
          break;
      }
      /*
      2-(b) その経路上に空き容量のないリンクが存在する場合、呼損とし、
      その時点までの「確立できた通信回数」をsum_successに足して、while文をbreakする
       */
      if (tmp < 0) {
        miss = 1;
        sum_success += success;
      } else {
        success++;
      }
    } /* while(miss == 0) */
  } /* for (sim_time = 0; ;) */ /* 1～3の手続きを1000回行うためのfor文 */
  /* シミュレーション評価の結果出力 */
  printf("\naverage = %f\n", (double)sum_success / N); /* 初めて呼損が起こるまでに確立できた通信回数の平均を表示 */
  return 0;
}
/* end */