askisi1.c

dynamic programming fastest path

#include <stdio.h>
#include <conio.h>

void main()
{

                                     /*dhlosh metablhton*/

 int AKB[50];/*apothikeuei ton arithmo twn kombwn se kathe bathmida*/
 int KSK[50][50][50]; /*apothjkeuei an uparxei metabash apo kombo mias bathmidas se kombo ths epomenhs*/
 int BD[50][50]; /*apothikeuei thn thesi tou kombou pou brisketai sth beltisth diadromh*/
 int KTK[50][50]; /*KOSTOS TELIKHS KATASTASHS,to elaxisto kostos se kathe kombo*/
 int KD[50][50][50]; /*kostoi diadromhs*/
 
 int n,ab,ek,tk,eb,C,i,j;

                                /*arxikopoihsh metablhton*/
 
 ab=0; /*arithmos bathmidwn*/
 n=0; /*bathmida n (trexousa vathmida)*/
 ek=0; /*epomenos kombos*/
 tk=0; /*trexon kombos*/
 eb=0; /*bathmida n+1 (epoKSKenh vathKSKida)*/
 C=0; /*dinei ta kosth metabashs stous kombous, dhladh ta kosth telikhs katastashs opws diamorfwnontai*/

 clrscr();

 printf("plhktrologiste ton arithmo twn aritmo twn bathmidwn toy susthmatos\n");
 scanf("%d",&ab);
  
 
          /*twra tha pliktrologoume ton arithmo twn kombwn sthn ekastote bathmida*/

 for(i=1;i<ab+1;i++)
 {
	printf("Doste ton arithmo ton komvwn tis bathmidas  %d \n",i);
	scanf("%d",&AKB[i]);
 }

             /*twra tha pliktrologhsoume poies diadromes uparxoun sto problhma*/

for (n=1;n<ab;n++)
	for(tk=1;tk<AKB[n]+1;tk++)
		for(ek=1;ek<AKB[n+1]+1;ek++)
		{
		  eb=n+1;

		  printf("an iparxei metabasi apo kombo %d ths bathmidas %d \n pros ton kombo %d ths bathmidas %d \n     
			  plhktrologiste 1 an oxi pliktrologiste 0 \n",tk,n,ek,eb);

		  scanf("%d",&KSK[n][tk][ek]);

		}

                           /*dinoume ta kosth diadromhs (an uparxei) an den uparxei i diaromh san kostos kataxwreite                                                                                                  megalos arithmos*/

for (n=1;n<ab;n++)
	for(tk=1;tk<AKB[n]+1;tk++)
		for(ek=1;ek<AKB[n+1]+1;ek++)
		{
			eb=n+1;

			if ( KSK[n][tk][ek]==1)
			{
			 printf("Doste to kostos diadromhs apo ton kombo %d  ths bathmidas %d pros ton kombo %d ths bathmidas %d\n",tk,n,ek,eb);

			 scanf("%d",&KD[n][tk][ek]);
			}
			else
			{
			KD[n][tk][ek]=1000;
			}
		}

                          /*zhtame to pithano kostos ston teleutaio kombo*/

printf("pliktrologeiste ena pithano kostos tou telikou kombou \n");
scanf("%d",&KTK[ab][1]);

                     
			/*efarmogh ths arxhs tou beltistou sel 1.1 shmeiwseis*/

for (n=(ab-1);n>0;n--)
	for(tk=1;tk<AKB[n]+1;tk++)
	{
		  C=150000; /*bazoume ena polu megalo arithmo gia na mpainei panta ston arxiko elegxo*/

		for(ek=1;ek<AKB[n+1]+1;ek++)
		{

		/*edw briskoume ta elaxista kostoi diadromhs pros ton kathe kombo*/


           if (   (KD[n][tk][ek]+KTK[n+1][ek])<C  )
			  {
				   C=KD[n][tk][ek]+KTK[n+1][ek]; /*edw tou leme pws to kostos telikhs katastashs n einai iso                                                            me to kostos diadromhs apo to n pros to n+1 sun to kostos telikhs                                                                                                             katastashs n+1 */
				   BD[n][tk]=ek;            /*edw apothikeuetai o epomenos kombos me thn mikroterh timh C*/
			  }
		}

			 KTK[n][tk]=C;
	}

	                 /*synexeia tou arxikou for gia thn emfanish sthn othonh tou elaxistou kostous kai ths beltisths                            diadromhs opou i beltisth diadromh orizetai apo tous kombous me ta mikroterea kosth telikhs                                                                                                              katastashs */
    clrscr();
	
	   printf("\n To kostos telikhs katastashs tou arxikou kombou einai %d\n",KTK[1][1]);


	printf("\n O beltistos dromos einai \n");
	tk=1;
	for(n=1;n<ab;n++)
	{
		printf("Apo ton kombo %d ths bathmidas %d odhgoumaste ston kombo %d ths bathmidas %d  \n",tk,n,BD[n][tk],n+1);

		tk=BD[n][tk];
	}
                                  /*epeidh den xwrane ola sthn othonh*/

	printf("\n Gia na synexisoume ta elaxista kostoi diadromhs pliktrologiste 1 \n");
	
	scanf("%d",&j);
        
        clrscr();
	
        printf("\n Ta elaxista kostoi metabashs gia kathe kombo einai\n\n");

	for (n=1;n<ab+1;n++)
		for(tk=1;tk<AKB[n]+1;tk++)
			printf("to elaxisto kostos telikhs katastashs tou komvou %d ths vathmidas %d einai %d \n",tk,n,KTK[n][tk]);


}