/*
  gcc -g wf3.cpp -o fw3
 
  ワーシャル-フロイド法(その3)
 
  スタックオーバーフローが怖いのと処理が遅くなりそうなので、「再帰呼出し」を使わない方法
  (http://www.kobore.net/diary_techno/?date=20180306)
 
  参考：ゼオスTTのブログ
  http://zeosutt.hatenablog.com/entry/2015/05/05/045943
 
*/
 
#include <stdio.h>
 
int d[5][5];  // d[i][k]：ノードiからノードkへの距離 
int next[5][5];  // ノードi から ノードj への最短経路における i の1つ後のノード
 
int main(void)
{
 
  // 変数の初期化
  for(int i = 0; i < 5; i++){
	for(int j = 0; j < 5; j++){
	  d[i][j] = 99999999; // 距離の初期化(でっかい値を入力しておく(INT_MAXは足し算の時に桁上がりが起こるので使わない)
	  next[i][j] = j; // ノードi から ノードj への最短経路における i の1つ後のノード
	}
  }
 
 
  // 確認用の表示
  printf("\n[STEP1]\n");
 
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]):%d\t",i,k,d[i][k]);
	  printf("next[%d][%d]):%d\n",i,k,next[i][k]);
	}
  }
 
  //// ここからは実際の距離を手書き
 
  for(int i = 0; i < 5; i++){
	d[i][i] = 0; //// 同じノードへの距離は0になるので、上書き
  }
 
  d[0][2] = 1;  // ノード0からノード2までの距離 1 を上書き
  d[2][0] = 1;  // その逆順(さぼってはダメ)
 
  d[0][1] = 2;  // ノード0からノード1までの距離 2 を上書き
  d[1][0] = 2;  // その逆順
 
  d[0][4] = 6;
  d[4][0] = 6;
  
  d[1][2] = 4;
  d[2][1] = 4;
  
  d[2][3] = 4;
  d[3][2] = 4;
 
  d[3][4] = 2;
  d[4][3] = 2;
  
  // 確認用の表示
  printf("\n[STEP2]\n");
 
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]):%d\t",i,k,d[i][k]);
	  printf("next[%d][%d]):%d\n",i,k,next[i][k]);
	}
  }
 
  // 経路長計算
  for (int k =0; k < 5; k++){
	for (int i =0; i < 5; i++){
	  for(int j = 0; j < 5; j++){
		if(d[i][j] > d[i][k] + d[k][j]){
 
		  d[i][j] = d[i][k] + d[k][j];
		  next[i][j] = next[i][k]; //更新処理
		}
	  }
	}
  }
 
  // 計算結果
  printf("\n[STEP3]\n");
 
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]):%d\t",i,k,d[i][k]);
	  printf("next[%d][%d]):%d\n",i,k,next[i][k]);
	}
  }
 
  // 経路パス表示
 
  printf("\n[Path]\n");
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  
	  int cur;
	  printf("d[%d][%d]: ",i,k);
	  
	  for (cur = i; cur != k; cur = next[cur][k]){
        printf("%d -> ", cur);
	  }
	  printf("%d\n", k);
	}
  }
}