#include<stdio.h>
#include<stdlib.h>
#include<values.h>
#define ng1 n
#if 1
 #define n 1001               // nombre de sommets du graphe
 #define a 835                // nombre d'arcs du graphe
 #define initg2 initg2_23(g2)
 typedef short int sommet;    // Les numéros de sommet sont des entiers codés sur 16 bits.
 sommet depart=7, arrivee=1;
#elif 0
 #define n 100000
 #define a 103333
 #undef ng1
 #define ng1 1
 #define initg2 initg2_352(g2,poids)
 typedef int sommet;          // Les numéros de sommet sont des entiers codés sur 32 bits.
 sommet depart=10001, arrivee=10000;
#else
 #define n 4
 #define a 8
 #define initg2
 typedef short int sommet;
 sommet depart=1, arrivee=0;
#endif

typedef char bool;           // les booléens, qui valent 0 ou 1 seront des entiers sur un octet.

typedef bool graphe1[ng1][ng1];// Un graphe1 est une matrice nxn de booléens.  g1[i][j]  ssi   i-->j est un arc

typedef struct {sommet ori, ext;} graphe2[a];  // Un graphe2 est un tableau de a arcs. Les arc sont g2[k].ori-->g2[k].ext
typedef int tetesuite[n+a];                    // int tete[n], suite[a];  avec suite=tete+n
                                               //  Les arcs partants de i sont tete[i], suite[tete[i]], suite[suite[tete[i]]], ...

typedef struct chainon *liste;            // Une liste est un pointeur sur un chaînon
struct chainon {sommet s; liste suite;};  // qui contient un sommet et le pointeur sur le chaînon suivant.
typedef liste graphe3[n];                 // Un graphe3 est un tableau de n listes chaînées de sommets.
                                          // Les successeurs du sommet i sont g3[i]->s, g3[i]->suite->s, g3[i]->suite->suite->s, ...
//
//    Affichage des graphes pour chacune des trois représentations.
//
void affg1(graphe1 g)
{ sommet i,j;                // pour tout couple de sommets (i,j) si g[i][j], c'est-à-dire si i-->j est un arc, on l'affiche
  for(i=0;i<n;i++) for(j=0;j<n;j++) if(g[i][j]) printf("%d-->%d   ", i, j);
  printf("\n");
}
void affg2(graphe2 g)
{ int k;                     // pour tout k de 0 à a-1 on affiche le kième arc g[k].ori-->g[k].ext
  for(k=0;k<a;k++) printf("%d-->%d   ", g[k].ori, g[k].ext);
  printf("\n");
}
void affg3(graphe3 g)
{ sommet i;                  // pour chaque sommet i, p décrit la liste des arcs partant de i, ce qui permet d'afficher l'arc i-->p->s
  liste p;
  for(i=0;i<n;i++) for(p=g[i];p;p=p->suite) printf("%d-->%d   ", i, p->s);
  printf("\n");
}
//
//     Conversion entre les trois représentations de graphes
//
void g1g2(graphe1 g1, graphe2 g2) // remplit g2 à partir de g1
{ sommet i,j;                     // pour tout couple de sommets (i,j) si g[i][j], c'est-à-dire si i-->j est un arc, on l'ajoute dans g2
  int k=0;
  for(i=0;i<n;i++) for(j=0;j<n;j++) if(g1[i][j]) g2[k].ori=i, g2[k++].ext=j;
}
void g2g1(graphe2 g2, graphe1 g1) // remplit g1 à partir de g2
{ sommet i,j;
  int k;
  for(i=0;i<n;i++) for(j=0;j<n;j++) g1[i][j]=0;  // On remplit la matrice de 0
  for(k=0;k<a;k++) g1[g2[k].ori][g2[k].ext]=1;   // Pour chaque arc i-->j dans g1[i][j] on remplace le 0 par un 1.
}
void g1g3(graphe1 g1, graphe3 g3) // remplit g3 à partir de g1
{ sommet i,j;
  for(i=0;i<n;i++) g3[i]=0;                       // Initialement la liste des arcs partant de tout sommet est vide.
  for(i=0;i<n;i++) for(j=0;j<n;j++) if(g1[i][j])  // Pour tout arc i-->j
  { liste p=malloc(sizeof(*p));                   //   p est un nouveau chaînon
    p->s=j;                                       //   contenant le sommet j
    p->suite=g3[i], g3[i]=p;                      //   que l'on rajoute en tête de la liste des arcs partant du sommet i
  }
}
void g3g1(graphe3 g3, graphe1 g1) // remplit g1 à partir de g3
{ sommet i,j;
  liste p;
  for(i=0;i<n;i++) for(j=0;j<n;j++) g1[i][j]=0;             // On remplit la matrice de 0
  for(i=0;i<n;i++) for(p=g3[i];p;p=p->suite) g1[i][p->s]=1; // Pour chaque arc i-->j dans g1[i][j] on remplace le 0 par un 1.
}
void g3g2(graphe3 g3, graphe2 g2) // remplit g2 à partir de g3
{ sommet i;                       // pour chaque sommet i, p décrit la liste des arcs partant de i, ce qui permet d'ajoute l'arc i-->p->s dans g2
  int k=0;
  liste p;
  for(i=0;i<n;i++) for(p=g3[i];p;p=p->suite) g2[k].ori=i, g2[k++].ext=p->s;
}
void g2g3(graphe2 g2, graphe3 g3) // remplit g3 à partir de g2
{ int k;
  sommet i;
  for(i=0;i<n;i++) g3[i]=0;            // Initialement la liste des arcs partant de tout sommet est vide.
  for(k=0;k<a;k++)                     // Pour tout arc i-->j   (en fait i=g2[k].ori et j=g2[k].ext)
  { liste p=malloc(sizeof(*p));        //   p est un nouveau chaînon
    p->s=g2[k].ext;                    //   contenant le sommet j
    p->suite=g3[i=g2[k].ori];          //   que l'on rajoute en tête de la liste des arcs partant du sommet i
    g3[i]=p;
  }
}
//
//      Chaînage des arcs partant d'un même sommet pour la représentation graphe2
//
void g2ts(graphe2 g2, tetesuite tete)  // remplit tete et suite à partir de g2
{ int k, *suite=tete+n; // les deux tableaux int tete[n], suite[a]; sont consécutifs en mémoire et forment donc un seul tableau de taille n+a
  sommet i;
  for(i=0;i<n;i++) tete[i]=-1;         // Initialement la liste des arcs partant de tout sommet est vide.
  for(k=0;k<a;k++) suite[k]=tete[i=g2[k].ori], tete[i]=k; // On ajoute l'arc k en tête de la liste des arcs partant de i=g2[k].ori
}
//
//      Parcours en profondeur d'abord (Depth First Search) pour chacune des trois représentations des graphes.
//
void dfs1(sommet s,graphe1 g,bool visite[n])
{ if(!visite[s])                  // Si le sommet s n'a pas encore été visité
  { sommet t;
    visite[s]=1;                  // on note que maintenant il a été visité puis
    for(t=0;t<n;t++) if(g[s][t])  // chaque de successeur t de s
     dfs1(t,g,visite);            // est visité
  }
}
void dfs3(sommet s,graphe3 g,bool visite[n])
{ if(!visite[s])              // Si le sommet s n'a pas encore été visité
  { liste p;
    visite[s]=1;              // on note que maintenant il a été visité puis
    for(p=g[s];p;p=p->suite)  // chaque de successeur de s
     dfs3(p->s,g,visite);     // est visité
  }
}
void dfs2(sommet s,graphe2 g,tetesuite tete,bool visite[n])
{ if(!visite[s])                    // Si le sommet s n'a pas encore été visité
  { int k, *suite=tete+n;
    visite[s]=1;                    // on note que maintenant il a été visité puis
    for(k=tete[s];k>=0;k=suite[k])  // pour chaque arc k partant de s
     dfs2(g[k].ext,g,tete,visite);  // on visite son extrémité
  }
}
//
//      Retournement du sens des arcs pour chacune des trois représentations des graphes
//
void retg1(graphe1 g)  // change le sens du graphe : l'arc i-->j devient l'arc j-->i
{ int i,j;
  for(i=0;i<n;i++)     // Pour tout couple de sommets (i,j) avec i>j 
  for(j=0;j<i;j++)
  { bool x=g[i][j];    //  on échange les valeurs de g[i][j] et g[j][i]
    g[i][j]=g[j][i];
    g[j][i]=x;         // Si on oublie la condition i>j, les deux variables g[1][2] et g[2][1] seront échangées deux fois,
  }                    // pour (i,j)=(1,2) et (i,j)=(2,1), et elles reprendront leur valeur initiale.
}
void retg2(graphe2 g)  // change le sens du graphe : l'arc i-->j devient l'arc j-->i
{ int k;
  for(k=0;k<a;k++)     // Pour chacun des a arcs g[k]
  { sommet x=g[k].ori; //  on échange son origine et son extrémité.
    g[k].ori=g[k].ext;
    g[k].ext=x;
  }
}
void retg3(graphe3 g)  // change le sens du graphe : l'arc i-->j devient l'arc j-->i
{ graphe3 h;
  sommet i;
  liste l;
  for(i=0;i<n;i++) h[i]=g[i], g[i]=0; // On met tous les arcs de g dans le graphe h, et g n'a plus d'arc.
  for(i=0;i<n;i++) for(l=h[i];l;)     // Pour chaque sommet i et chaque arc l (ou p) partant de i, on l'enlève de h et on l'ajoute retourné dans g.
  { liste p=l;                        //   Le chaînon à déplacer p
    sommet j=p->s;                    //   représente un arc de i vers j dans le graphe h.
    l=p->suite;                       //   On l'enlève de la liste l des successeurs de i dans h.
    p->s=i;                           //   On l'utilise pour représenter que i est un successeur de j dans g. (la nouvelle extrémité est i)
    p->suite=g[j], g[j]=p;            //   On insère le chaînon p en tête de la liste g[j] des arcs partant du sommet j dans le graphe g.
  }
}
//
//      Parcours itératifs de graphe pour la représentation graphe3
//      bfs            : en largeur d'abord (Breadth First Search) avec une file d'attente  
//      dfs et dfspile : en profondeur d'abord (Depth First Search) avec et sans pile  
//
void bfs(graphe3 g, sommet depart, int dist[n], sommet pere[n])
{ sommet file[n], y;
  int debf=0, finf=0;                    // La file d'attente est initialement vide.
  liste l;
  for(y=0;y<n;y++) dist[y]=pere[y]=n;    // aucun sommet n'a encore été visité
  pere[depart]=depart;                   // Le sommet de départ est la racine de l'arbre de parcours, il n'a pas de père.
  dist[depart]=0;                        // Il est à une distance 0 de lui-même.
  file[finf++]=depart;                   // On le met dans la file d'attente des sommets ouverts.
  while(debf<finf)                       // Tant que la file n'est pas vide
  { sommet x=file[debf++];               //   on sort x de la file d'attente
    for(l=g[x];l;l=l->suite)             //   pour chacun des arcs partant de x
    if(pere[y=l->s]==n)                  //   qui mène à un sommet y non encore visité,
    { pere[y]=x;                         //     On note qu'il est visité en notant son père
      dist[y]=dist[x]+1;                 //     et sa distance au sommet de départ.
      file[finf++]=y;                    //     On le met dans la file d'attente
    }
  }
}
void dfspile(graphe3 g, sommet depart, int dist[n], sommet pere[n])
{ sommet pile[n], y;
  graphe3 h;
  int hauteur=0;                         // La pile est initialement vide.
  for(y=0;y<n;y++) dist[y]=pere[y]=n,    // Aucun sommet n'a encore été visité
                   h[y]=g[y];            // tous les arcs sont encore utilisables.
  pere[depart]=depart;                   // Le sommet de départ est la racine de l'arbre de parcours, il n'a pas de père.
  dist[depart]=0;                        // Il est à une distance 0 de lui-même.
  pile[hauteur++]=depart;                // On le met dans la pile des sommets ouverts.
  while(hauteur)                         // Tant que la pile n'est pas vide
  { sommet x=pile[--hauteur];            //   on sort x de la pile
    liste l=h[x];                        //   l est la liste des arcs partant de x qui n'ont pas encore été utilisés
    if(l)                                //   Si cette liste n'est pas vide,
    { h[x]=l->suite;                     //     on va utiliser son premier élément, qu'on enlève donc de la liste
      pile[hauteur++]=x;                 //     On remet x dans la pile
      if(pere[y=l->s]==n)                //     Si l'arc l mène à un sommet y non encore visité,
      { pere[y]=x;                       //       On note qu'il est visité en notant son père
        dist[y]=dist[x]+1;               //       et sa distance au sommet de départ (dans l'arbre de parcours)
        pile[hauteur++]=y;               //       et on le met dans la pile
      }
    }
  }
}
void dfs(graphe3 g, sommet x, int dist[n], sommet pere[n])
{ sommet y;
  graphe3 h;
  for(y=0;y<n;y++) dist[y]=pere[y]=n,    // Aucun sommet n'a encore été visité.
                   h[y]=g[y];            // Tous les arcs sont encore utilisables.
  pere[x]=x;                             // Le sommet de départ est la racine de l'arbre de parcours. Il n'a pas de père.
  dist[x]=0;                             // Il est à une distance 0 de lui-même.
  for(;;)                                // Tant qu'on a pas fini
  { liste l=h[x];                        //   l est la liste des arcs partant de x qui n'ont pas encore été utilisés.
    if(l)                                //   Si cette liste n'est pas vide,
    { h[x]=l->suite;                     //     on va utiliser son premier élément, qu'on enlève donc de la liste.
      if(pere[y=l->s]==n)                //     Si l'arc l mène à un sommet y non encore visité,
      { pere[y]=x;                       //       On note qu'il est visité en notant son père
        dist[y]=dist[x]+1;               //       et sa distance au sommet de départ (dans l'arbre de parcours)
        x=y;                             //       et on avance sur ce sommet.
      }
    } else                               //   Quand on a regardé tous les arcs partant de x,
    if(pere[x]==x) break;                //   si de plus x est le sommet de départ, alors on a fini,
    else x=pere[x];                      //   sinon on recule.
  }
}
//
//  recherche d'un cycle dans un graphe représenté par graphe2
//
typedef enum{libre, ouvert, ferme} statut[n];  // Chaque sommet peut être libre, ouvert ou fermé
int arr(graphe2 g, sommet pere[n])             // Rend un arc arrière dans la forêt correspondant à pere.
{ tetesuite tete;
  statut stat;
  int arr=n, *suite=tete+n;                    // Rend n s'il n'y a pas de cycle
  void parcours(sommet s)                      // Procédure récursive, s est un sommet libre
  { sommet t;                                  //   t est un des sommets successeurs de s
    int k;                                     //   k est un des arcs partant du sommet s
    stat[s]=ouvert;                            //   s sera ouvert jusqu'à la fin de l'exécution de cette procédure
    for(k=tete[s];k>=0;k=suite[k])             //   Pour chaque arc k partant du sommet s
    switch(stat[t=g[k].ext])                   //      et arrivant sur le sommet t,
    { case libre : pere[t]=s; parcours(t); break; //   si t est libre, on va le visiter ( en mettant l'arc s-->t dans l'arbre de parcours)
      case ouvert: arr=k;                      //      si t est ouvert, on a trouvé un arc arrière k : s-->t    
      default: ;                          
    }
    stat[s]=ferme;                             //   On a exploré s et tous ses successeurs
  }
  sommet s;
  g2ts(g,tete);                                //  On construit les listes d'adjacence, à partir de la liste de tous les arcs.
  for(s=0;s<n;s++)    stat[s]= libre;          //  Tous les sommets sont initialement libres
  for(s=0;s<n;s++) if(stat[s]==libre) pere[s]=s, parcours(s); // On fait un parcours en profondeur à partir de sommets libres
  return arr;                                  //  On rend le dernier arc arrière trouvé ou n s'il n'y en a pas.
}
void affcycle(graphe2 g, sommet pere[n], int k) // Affiche un cycle, en affichant à l'envers la branche de l'arbre de parcours
{ sommet x=g[k].ori, t=g[k].ext;                //  reliant l'extrémité d'un arc arrière à l'origine de cet arc.
  for(;x!=t;x=pere[x]) printf("%d ",x);
  printf("%d\n",x);
}
//
//    Recherche des composantes fortement connexes d'un graphe représenté par graphe2
//
int cherchecfc(graphe2 g2,int cfc[n])
{ int finvisite[n], nbfin=0, tete[n+a], *suite=tete+n, nbcfc=0;
  void parcours1(sommet s)
  { int k;
    sommet t;
    cfc[s]=-1;   // on note que s a déjà été visité
    for(k=tete[s];k>=0;k=suite[k]) if(!cfc[t=g2[k].ext]) parcours1(t);
    finvisite[nbfin++]=s;
  }
  void parcours2(sommet s)
  { int k;
    sommet t;
    cfc[s]=nbcfc;              // on note que s a déjà été visité
    for(k=tete[s];k>=0;k=suite[k]) if(cfc[t=g2[k].ext]<0) parcours2(t);
  }
  int i;
  g2ts(g2,tete);               // chaînage des arcs sortant de chacun des sommets
  for(i=0;i<n;i++) cfc[i]=0;   // aucun sommet n'a encore été visité
  for(i=0;i<n;i++) if(!cfc[i]) parcours1(i);
  retg2(g2);                   // retournement du graphe
  g2ts(g2,tete);               // chaînage des arcs entrant dans chacun des sommets
  while(nbfin) if(cfc[i=finvisite[--nbfin]]<0) parcours2(i), nbcfc++;
  retg2(g2);                   // retournement du graphe
  return nbcfc;
}
//
//  Recherche du plus court chemin dans un graphe orienté valué positivement par la méthode de Dijkstra avec un tas
//
typedef struct {int nn, *t, *pos, *dist;} tas;
void echange(tas t,int i,int j)
{ int x=t.t[i], y=t.t[j];
  t.t[i]=y, t.pos[y]=i;
  t.t[j]=x, t.pos[x]=j;
}
#define le(i,j) (t.dist[t.t[i]]<=t.dist[t.t[j]])
void remonte(tas t,int j)
{ for(;;)
  { int jj=j/2;
    if(!jj) return;
    if(le(jj,j)) return;
    echange(t,j,jj);
    j=jj;
  }
}
void descend(tas t,int j)
{ for(;;)
  { int jj=j+j;
    if(jj>t.nn) return;
    if(jj<t.nn && le(jj+1,jj)) jj++;
    if(le(j,jj)) return;
    echange(t,j,jj);
    j=jj;
  }
}
#undef le
int otepp(tas *t)
{ echange(*t,1,t->nn--);
  descend(*t,1);
  return t->t[t->nn+1];
}
void dijkstra(graphe2 g2, int poids[n], sommet dep, int dist[n])
{ int tete[n+a], *suite=tete+n, pos[n], tt[n+1], i, k;
  tas t={n,tt,pos,dist};
  g2ts(g2,tete);
  for(i=0;i<n;i++) tt[pos[i]=i+1]=i, dist[i]=MAXINT;
  echange(t,1,dep+1);
  dist[dep]=0;
  while(t.nn && dist[i=otepp(&t)]!=MAXINT)
   for(k=tete[i];k>=0;k=suite[k]) 
   { sommet j=g2[k].ext;
     int d=dist[i]+poids[k];
     if(d<dist[j]) dist[j]=d, remonte(t,pos[j]);
   }
}
//
//   initialisation des graphes
//
void initg2_23(graphe2 g2)
{ int k=0, i,j;
  printf("arcs  2i --> i   et  i --> 3i+1\n");
  for(i=0;j=i+i  ,j<n;i++) g2[k].ori=j, g2[k++].ext=i;
  for(i=0;j=3*i+1,j<n;i++) g2[k].ori=i, g2[k++].ext=j;
  printf("n=%d k=%d a=%d\n",n,k,a);
  if(k!=a) exit(1);
}
void initg2_352(graphe2 g2,int poids[n])
{ int i, k=0;
  printf("arcs  i --> 3i+1  et  i --> 5i+1  et  2i --> i  de poids respectifs 2, 11 et 1\n");
  for (i=0;3*i+1< n;i++) g2[k].ori=i,   g2[k].ext=3*i+1, poids[k++]=2;
  for (i=0;5*i+1< n;i++) g2[k].ori=i,   g2[k].ext=5*i+1, poids[k++]=11;
  for (i=0;2*i  < n;i++) g2[k].ori=2*i, g2[k].ext=i,     poids[k++]=1;
  printf("n=%d k=%d a=%d\n",n,k,a);
  if(k!=a) exit(1);
}

int main()
{ int i, ng;
  graphe2 g2={{0,1},{1,2},{2,3},{0,3},{1,0},{2,1},{1,3},{2,0}}, h2, k2;
  int poids[a]={5  ,  10 ,  4  ,  8  ,  1  ,  6  ,  1  ,  3  }, dist[n], cfc[n];
  graphe1 g1, h1;
  graphe3 g3, h3;
  void (*tfs[])(graphe3 g,sommet depart, int dist[n], sommet pere[n])={bfs,dfs,dfspile};
  for(i=8;i<a;i++) poids[i]=1;
  initg2;
  if(n<10000) printf("Il y a %d composantes fortement connexes\n",cherchecfc(g2,cfc));
  for(i=0;i<a && i<100;i++) printf("%3d     ",poids[i]);
  printf("\n");
  if(n<100)
  { affg2(g2);
    g2g1(g2,g1), printf("g2g1  :  "), affg1(g1);
    g1g2(g1,h2), printf("g1g2  :  "), affg2(h2);
    g2g3(g2,g3), printf("g2g3  :  "), affg3(g3);
    g3g2(g3,k2), printf("g3g2  :  "), affg2(k2);
    g3g1(g3,h1), printf("g3g1  :  "), affg1(h1);
    g1g3(g1,h3), printf("g1g3  :  "), affg3(h3);
  }
  for(ng=n!=ng1;ng<3;ng++)
  { bool visite[n];
    for(i=0;i<n;i++) visite[i]=0;
    switch(ng)
    { case 0: dfs1(2,g1,visite); break;
      case 2: dfs3(2,g3,visite); break;
      case 1: {tetesuite ts; g2ts(g2,ts); dfs2(2,g2,ts,visite);} break;
    }
    for(i=0;i<n;i++) if(visite[i]) printf(" %d ",i);
    printf("\n");
  }
  for(ng=0;ng<3;ng++)
  { int dist[n];
    sommet pere[n];
    tfs[ng](g3,2,dist,pere);
    for(i=0;i<n && i<100;i++) printf(" %d-->%d(%d) ",pere[i],i,dist[i]);
    printf("\n");
  }
  if(n<10000)
  { sommet pere[n];
    int k=arr(g2,pere);
    if(k==n) printf("pas de cycle\n");
    else     affcycle(g2,pere,k);
  }
  retg2(g2);
  dijkstra(g2,poids,arrivee,dist);
  retg2(g2);
  for(i=0;i<n && i<100;i++) printf("%d ",dist[i]);
  printf("\n");
  { int tete[n+a], *suite=tete+n, s,k;
    g2ts(g2,tete);
    for(k=tete[s=depart];k>=0;k= dist[g2[k].ext]+poids[k]==dist[s]
                               ? printf(" %d(%d)",s,dist[s]), tete[s=g2[k].ext]
                               : suite[k]) ;
    printf(" %d(%d)\n",s,dist[s]);
  }
  return 0;
}