#include <iostream>
#include <vector>

using namespace std;

const int N=6;
const int INF=9999;                      //La valeur infinie.

void floydWarshall(int longueur[][N],int dist[][N],int P[][N]);
void affichage(int dist[][N],int chemin[][N]);
void itineraire(int i,int j,int chemin[][N]);
void itineraireville(int i,int j,int chemin[][N]);
void fermeturetrans(int longueur[][N], int dist[][N], int P[][N], bool fermeture[][N]);
void affichagematrice(int n, bool mat[][N]);

int main(){
   int longueur[N][N]={{INF,INF,INF,2,INF,2},   //Les longueurs des arcs.
	 	      {2,INF,2,2,INF,INF}, //longueur[i][j]=INF si l'arc ij n'existe pas
	 	      {INF,INF,INF,2,INF,INF},
	 	      {INF,INF,INF,INF,2,2},
	 	      {INF,INF,2,INF,INF,2},
          {INF,INF,2,INF,INF,INF}};
  int dist[N][N];                        //Le tableau des distances.
  int chemin[N][N];                      //Le tableau de la premiere etape du chemin de i a j.
  bool ferm[N][N];
  fermeturetrans(longueur,dist,chemin,ferm);
  affichagematrice(N,ferm);
  return 0;
}

void affichagematrice(int n, bool mat[][N]){
  for (int i = 0; i < n; i ++) {
    cout<<"[ ";
    for (int j = 0 ; j < n; j ++){
      cout<<mat[i][j]<<" , ";
    }
    cout << " ]"<<endl;
  }
}

void fermeturetrans(int longueur[][N], int dist[][N], int P[][N], bool fermeture[][N]){
  for (int i =0; i < N; i ++){
    dist[i][i]=0;
    P[i][i]=i;
    for (int j = 0 ; j < N; j ++){
      if (longueur[i][j]!=INF){
        dist[i][j]=longueur[i][j];
        P[i][j]=j;
        fermeture[i][j]=true;
      }
      else {
        dist[i][j]=INF;
        P[i][j]=-1;
        fermeture[i][j]=false;
      }
    }
  }
    for (int k = 0; k < N; k++){
      for(int i =0; i < N; i ++ ){
        for (int j = 0 ; j < N; j ++){
          if (dist[i][j]>dist[i][k]+dist[k][j]){
            dist[i][j]=dist[i][k]+dist[k][j];
            P[i][j]=P[i][k];
            fermeture[i][j]=true;
          }
        }
      }
    }
    for (int i =0; i < N; i ++){
      if (dist[i][i]<0){
        std::cout<<"Il existe un cycle orienté de poids <0"<<endl;
      }
    }
  }