/*
  gcc -g wf.cpp -o fw
 
  ワーシャル-フロイド法
  (ダイクストラは個別ルートでは早いが、先に全ルート計算しておくなら、
  こっちの方法の法が速いこともある)
 
  参考：ゼオスTTのブログ
  http://zeosutt.hatenablog.com/entry/2015/05/05/045943
 
*/
 
#include <stdio.h>
 
int d[5][5];  // d[i][k]：ノードiからノードkへの距離 
int via[5][5];  // d[i][k]の間にある(少くとも1つの)中継ノード
 
 
// 中継パスの表示ルーチン(再帰呼出し用)
void printPath1_aux(int begin, int end) {
  if (via[begin][end] == begin) {
	if (begin != end)
	  printf("%d -> ", begin);
	return;
  }
  
  printPath1_aux(begin, via[begin][end]);
  printPath1_aux(via[begin][end], end);
}
 
// 中継パスの表示ルーチン
void printPath1(int start, int goal) {
  printPath1_aux(start, via[start][goal]);
  printPath1_aux(via[start][goal], goal);
  printf("%d\n", goal);
}
 
int main(void)
{
 
  // 変数の初期化
  for(int i = 0; i < 5; i++){
	for(int j = 0; j < 5; j++){
	  d[i][j] = 99999999; // 距離の初期化(でっかい値を入力しておく(INT_MAXは足し算の時に桁上がりが起こるので使わない)
	  via[i][j] = i; // ノードiからノードkへの経由値の初期化 
	}
  }
 
 
  // 確認用の表示
  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("via[%d][%d]):%d\n",i,k,via[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("via[%d][%d]):%d\n",i,k,via[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];
		  via[i][j] = 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("via[%d][%d]):%d\n",i,k,via[i][k]);
	}
  }
 
  // 経路パス表示
 
  printf("\n[Path]\n");
  for(int i = 0; i < 5; i++){
	for(int k = 0; k < 5; k++){
	  printf("d[%d][%d]: ",i,k);
	  printPath1(i, k);
	}
  }
}