#include <cstdio>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <cmath>
#include <ctime>
#include <bitset>
#include <stdlib.h>
#include <stddef.h>
#include <float.h>


#define input "Dijkstra.in"      //Input file name
#define output "Dijkstra.out" 

#define infinity 1000000      // a big int
#define max_vertexes 10000
using namespace std;

typedef int Graph[max_vertexes][max_vertexes];           // the max count of vertexes

FILE *fin,*fout;
int probN,n,s,t=0;
Graph A;

int read_case()
{
   int i,j,k,m,tmp;
   if (feof(fin)) return 0;
   fscanf(fin,"%d %d",&n,&m);
   if (n==0) return 0;
   probN++;
   fscanf(fin,"%d %d",&s,&t);
   s--;t--;
   for (i=0;i<n;i++)
      for (j=0;j<n;j++)
         A[i][j]=infinity;
   printf("Graph %d:\n",probN);
   fprintf(fout,"Graph %d:\n",probN);
   for (k=0;k<m;k++)
   { fscanf(fin,"%d %d %d",&i,&j,&tmp);
     fprintf(fout,"V(%d)-V(%d):%d\n",i,j,tmp);
     printf("V(%d)-V(%d):%d\n",i,j,tmp);
     A[i-1][j-1]=tmp;
    }
   return 1;
}

int rand_num(int no[],int NUM )
{
    int cont[NUM];
    int index, i;
    for (i=0; i<NUM; i++)
    cont[i] = i;
    srand((int)time(0));
    for (i=0; i<NUM; i++) {
        index = (int)((float)(NUM-i) * rand() / (RAND_MAX+1.0));
        no[i]=cont[index];
        cont[index] = cont[NUM-1-i];
    }
}
int input_main()
{
    int pr,su,m=0;
    div_t tmp;
    printf("Combien sommet:");
    cin>>n;
    printf("Combien arc:");
    cin>>m;
    fprintf(fout,"\nAleatoire......:\nNombre de sommets:%d\n",n);
    printf("\nAleatoire......:\nNombre de sommets:%d\n",n);
    fprintf(fout,"Nombre d'arcs:%d\n",m);    
    printf("Nombre d'arcs::%d\n",m);
    s=0;t=n-1;
    int no1[m],no2[n];
    for (int i=0;i<n;i++)
      for (int j=0;j<n;j++)
         A[i][j]=infinity;
    rand_num(no1,m);
    rand_num(no2,n);
    srand((int)time(0));
    for (int k=0;k<m;k++)
    {
        tmp=div(no1[k],n);
        pr=int(tmp.rem);
        tmp=div((no2[k]+pr),n);
        su=int(tmp.rem);
        A[pr][su]=1 + (int)((float)100*rand() / (RAND_MAX + 1.0));
        fprintf(fout,"V(%d)-V(%d):%d\n",pr,su,A[pr][su]);
    }
}    
    
           
int path[max_vertexes],d[max_vertexes],mark[max_vertexes];

int Dijkstra()
{

    int i,j,w,minc;
    for (i=0;i<n;i++) mark[i]=0;
    for (i=0;i<n;i++)
        {   d[i]=A[s][i];
            path[i]=s;	}
    mark[s]=1;path[s]=0;d[s]=0;
    for (i=1;i<n;i++)
		{   minc=infinity;
          w=0;
          for (j=0;j<n;j++)
            if ((mark[j]==0)&&(minc>=d[j])) {minc=d[j];w=j;}
          mark[w]=1;
          for (j=0;j<n;j++)
            if ((mark[j]==0)&&(A[w][j]!=infinity)&&(d[j]>d[w]+A[w][j]))
                {   d[j]=d[w]+A[w][j];
                    path[j]=w;     }
      }
    return 1;
}

void print()
{
     fprintf(fout,"-----------------------------------------------------------\n");
     fprintf(fout,"Le plus court chemin entre la source et le sommet courant:\n");
     fprintf(fout,"-----------------------------------------------------------\n");
     printf("-----------------------------------------------------------\n");
     printf("Le plus court chemin entre la source et le sommet courant:\n");
     printf("-----------------------------------------------------------\n");
     for (int j=1;j<n;j++)
     {   
         int i=j;      
         while (i!=s)
               {
                     fprintf(fout,"%d<--",i+1);
                     printf("%d<--",i+1);
                     i=path[i];
               }
         fprintf(fout,"%d:%d\n",s+1,d[j]);
         printf("%d:%d\n",s+1,d[j]);
     }
}     
void solve_case()
{
    int i;
    time_t start,end;
    start=clock();
    Dijkstra();
    end=clock();
    print();
    fprintf(fout,"Le plus court chemin :");
    printf("Le plus court chemin :");
    i=t;
    while (i!=s)
    {
    fprintf(fout,"%d<--",i+1);
    printf("%d<--",i+1);
    i=path[i];
    }
    fprintf(fout,"%d\n\n",s+1);
    printf("%d\n\n",s+1);
    fprintf(fout,"Le temps d'execution:%f\n\n",difftime(end,start));
    printf("Le temps d'execution:%f\n\n",difftime(end,start));
}

void solve_case_input()
{
    int i;
    time_t start,end;
    start=clock();
    Dijkstra();
    end=clock();
    fprintf(fout,"-----------------------------------------------------------\n");
    fprintf(fout,"Le plus court chemin entre la source et le sommet courant:\n");
    fprintf(fout,"-----------------------------------------------------------\n");
    for (int j=1;j<n;j++)
    {   
        int i=j;      
        while (i!=s)
              {
                    fprintf(fout,"%d<--",i+1);
                    i=path[i];
              }
        fprintf(fout,"%d:%d\n",s+1,d[j]);
    }
    fprintf(fout,"Le plus court chemin :\n");
    printf("Le plus court chemin :\n");
    i=t;
    while (i!=s)
    {
    fprintf(fout,"%d<--",i+1);
    printf("%d<--",i+1);
    i=path[i];
    }
    fprintf(fout,"%d\n",s+1);
    printf("%d\n",s+1);
    fprintf(fout,"Le temps d'execution:%f ms\n",difftime(end,start)/1000);
    printf("Le temps d'execution:%f ms\n",difftime(end,start)/1000);
}

int main()
{
   char ch;
   while (1)
   {
   printf("\n1.Démonstration avec les paramètres importé ;\n2.Entrez les parametres à la main\n");
   printf("Quel choix vous désirez :");
   cin>>&ch;
    switch(ch)
    {
             case '1':
                  assert(fin=fopen(input,"r"));
                  assert(fout=fopen(output,"w"));   
                  while (read_case()) solve_case();
                  fclose(fin);
                  fclose(fout);
                  break;
                   
             case '2':
                  assert(fin=fopen(input,"r"));
                  assert(fout=fopen(output,"w"));  
                  input_main();
                  solve_case_input();
                  fclose(fin);
                  fclose(fout); 
                  break;
                  
             default:
                  printf("Input erreur\n");
                  break;
    } 
   }          
	return 0;
}