# include <stdio.h>
# define MAX_NODE 8
# define INFINITY 1000000

 int n, dist[MAX_NODE][MAX_NODE];

void Print_Matrix (int);



 struct state{
        int predecessor;
        int lenght;
        int label;
    }state [MAX_NODE];


 int main(){




    int  nodes ;
    int cont = 1;

    printf("enter the amount of nodes of matrix : \n");
    scanf("%d", &nodes);
    //printf("%d", nodes);

    printf("To assemble  distance matrix enter a value :[distance]\n");

    for(int line = 0; line < nodes; line++)
    {
        for(int column = 0; column < nodes ; column++)
        {
            printf("Establish a conect between %d --> %d [nodes] ? 0 to N : ",line,column);

              scanf("%d", &dist[line][column]);
        }
    }



    int  paht[MAX_NODE];

    int s,t;
    printf("Enter the origin and destination :");
    scanf("%d %d",&t ,&s);

    int i, k, min;
    struct state *p;

    for (p = &state[0]; p < &state[nodes]; p++){

        p->predecessor =-1;
        p-> lenght = INFINITY;
        p-> label = -1;
    }

    state[t].lenght = 0;
    state[t].label = 1;
    k = t;
    do{

        for (i = 0; i < nodes ;i++){
            if(dist[k][i] != 0 && state[i].label == -1){
                if(state[k].lenght + dist[k][i] < state[i].lenght){
                    state[i].predecessor = k;
                    state[i].lenght = state[k].lenght + dist[k][i];
                }
            }
        }

        k = 0;
        min = INFINITY;


        for(i = 0 ;i <  nodes ; i++){
            if(state[i].label == -1 && state[i].lenght < min  ){
                min = state[i].lenght;
                k = i;
                cont++;
            }
        }

        state[k].label = 1;

    }while(k != s);

    i = 0 , k = s;

    do{
        paht[i++] = k ;
        k = state[k].predecessor;//printf("%d", state[k].predecessor);

     }while(k >= 0);


    printf("Melhor Caminho :|Best paht : \n");

    int value = 0,h,g;

    for(i = 0;i <= s; i++){

        if(paht[i]!= t){
            printf("%d--> ",paht[i]);

        }else{
            break;
        }
    }

    printf("%d-->",t);
    printf("Start\n");

    for(i = 0;i <= s; i++){
        h = paht[i]; g = paht[i+1];
        if(paht[i]!= t){
            value += dist[g][h];
        }else{
            break;
        }

    }
    printf("Route Cost :%d\n",value);
    printf("jumps :%d",cont);
    /*
    printf("Distancias Percorridas|Distance traveled : \n");
    printf("Start");

        for (i = 0; i<=s ; i++  ){
            printf(" --> %d",state[i].lenght  );
    }
    printf("\n");
    */


    Print_Matrix(nodes);


    return 0;
 }

 void Print_Matrix(int n){
    printf("             Distance Matrix\n");
    printf("---------------------------------------------\n");
    int k = 1;

    printf("\t\t|  x|");
    for(int i = 0; i<= n ;i++){
        for(int j = 0; j<n; j++){
            if(i == 0){
                printf("|%3d|", j);
            }else{
                if(k == 1){
                    printf("\t\t|%3d|", i-1);
                    k--;
                }
                printf("|%3d|",dist[i-1][j] );

            }
        }
        printf("\n");

        k= 1;

    }
    printf("\n");

}