#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

#define maxcities 50  // the maximum number of cities I put it hear so I can change when I need to
#define mincities 5   //the minimum of cities
#define maxdis 20       //the maximum distance
#define impossible 10000 // the * dis value
#define big 100000
//This code by Ahmad Hamdan for the ITP2 Assignment

int adj[maxcities][maxcities];      //adjacency matrix
int noc=0, in = 0, d =0; // The Number of cities , initial city , destination city
int dist[maxcities], visited [maxcities], number_of_paths, path[maxcities], cnt; //distance matrix and the matrix of visited nodes and the matrix of all possible paths

void cntPaths(int node){        //count the all paths
    visited[node] = 1;          //mark the node a visited
    if(node == d)
        number_of_paths++;

    // iterate on the neighbors of node
    for(int i=0;i<noc;i++)
        if(!visited[i] && adj[i][node] != impossible && dist[i] == dist[node] + adj[i][node] && node != d)
            cntPaths(i);

    visited[node] = 0; // we are done with node so it is free now
}

void printPaths(int node){
    visited[node] = 1;      //mark the node a visited
    path[cnt++] = node;     // add the node to the shortest path
    if(node == d){          // we reached the destination so we print the path
        printf("%d. ", number_of_paths++);
        for(int i=0;i<cnt;i++){
            printf("%d", path[i]);
            if(i != cnt-1)
                printf(" -> ");
        }
        printf("\n");
    }

    // iterate on the neighbors of node
    for(int i=0;i<noc;i++)
        if(!visited[i] && adj[i][node] != impossible && dist[i] == dist[node] + adj[i][node] && node != d)
            printPaths(i);
    visited[node] = 0;
    cnt--;              // delete a node from the current shortest path
}

void dijkstra(int adj[maxcities][maxcities],int source,int dest){
int visited [maxcities];
int current,mindis, cnt = noc - 1;

// initializing values
for(int i=0;i<noc ;i++)
{
  dist[i]= adj[i][source];
  visited[i]=0;
}
visited[source]=1;
while(cnt){

    mindis = impossible;

    // selecting the minimum distance for an unvisited node
    for(int i=0;i<noc;i++){
        if(dist[i] < mindis && !visited[i]){
            mindis = dist[i];
            current = i;
        }
    }

    // updating distances of node's neighbors
    for(int i=0;i<noc;i++){
        if(!visited[i] && dist[current]+adj[i][current] < dist[i]){
            dist[i] = dist[current]+adj[i][current];
        }
    }

    // no path
    if(dist[dest] == impossible){
        printf("Initial and destination cities are not connected\n");
        exit(0);
    }
    cnt--;
}
}
int test(char s[], char e[])    //this function is just to test the number read from the input file as soon as it's read
{
    if (strlen(s)>1) // if it has more than one digit and the first one is zero this zero is insignificant
    {
       if (s[0]=='0')
       {
            printf("Insignificant zero in %s.", e);
            exit(1);
       }
       else for (int j =0; s[j] != '\0' ;j++) //if it has more than one character i should make sure that all of them are digits
       {
           if (!(isdigit(s[j]))) //I am using isdigit function
            {
               printf("Invalid number for %s.", e);
               exit(1);
            }
       }


    }

    if (strlen(s)==1) // if it is one digit only i have to make sure that it is either a digit or a star
    {
        if (!((isdigit(s[0])) || s[0]== '*' ))
        {
            printf("Invalid number for %s." , e);
            exit(1);
        }

    }
    if (strlen(s)==0) // if there is no number then it is a problem in the structure
    {
        printf("Invalid structure for %s." ,e);
        exit(1);
    }

    return 1;

}


int inrange (int a , int i, int j, char s[]) // this function's mission is just to make that a given value is in a range while given the range and a string defines what I am testing
{
    if (!(a>=i && a<=j))    // testing the range
    {
        printf("%s is out of range", s);
        exit(1);
    }
    return 1;
}

int more_than_one_space(char s[])   //testing the number of spaces if there is more than one it is an invalid structure
{
    if (strlen(s)>1)
    {
        printf("invalid structure.");
        exit(1);
    }
    return 1;
}


int not_star (char s[], char e[])   // testing if it is a star or nor
{
    if (s[0]=='*')
    {
        printf("Invalid value for the %s.", e);
        exit(1);
    }
    return 1;
}

int main()
{

    char s[1000];
    s[0]= '\0'; //setting the string to empty

    freopen("input.txt", "r", stdin); // Redirecting the input to input.txt so I can use manipulate the input as if am dealing with a standard input
    freopen("AhmadHamdanOutput.txt","w",stdout); // Redirecting the output to AhmadHamdan.txt so I can deal with the output easily as if I am dealing with the standard output
    scanf("%[^ ]", s);  //keeps scanning everything until it reaches a space
    test(s, "number of cities");    //testing it number of cities meets the requirements
    not_star(s,"number of cities");     //number of cities can never be a char
    noc =atoi(s);   //converting the number of cities from string to integer
    inrange(noc, 5, 50, "Number of cities" );     //testing if it is in range
    s[0]='\0';  //emptying the string
    scanf("%[ ]",s);    //scans all consecutive spaces
    more_than_one_space(s);     //not allowed to be more than one space
    s[0]='\0';
    scanf("%[^ ]",s);   //keeps scanning everything until it reaches a space
    test(s,"Initial city");
    not_star(s,"initial city");     //initial city can never a char
    in= atoi(s);
    inrange(in,0,noc-1,"initial city");   //initial city should be in range between 0 and number of cities -1
    s[0]='\0';
    scanf("%[ ]",s);
    more_than_one_space(s);
    s[0]='\0';
    scanf("%[^\n]",s);
    test(s,"destination city");
    not_star(s,"destination city");     //destination is never a star
    d=atoi(s);
    inrange(d,0,noc-1,"destination city");      //destination city is between 0 and number of cities -1
    s[0]='\0';
    ////////////////////////////////////////////////////////////////////////////// first line of input finished
    scanf("%[\n]",s);
    if (strlen(s) != 2){        //reading the empty line between the first and the third line
        printf("Invalid structure");
        exit(1);
    }
    s[0]='\0';

    int temp;
    for(int i=0;i<noc;i++)      // reading all elements of the adjacency matrix noc * noc
    {
        for(int j=0;j<noc;j++)
        {
            if(j==noc-1){ // after the last element of each row there is a new line thats why i am reading everything until
                scanf("%[^ \n]",s);
            }
            else
                scanf("%[^ ]",s); // not the last element so i am expecting a space after the element
            test(s,"distance");     //checking if the the element meets the requirements
            if (s[0]=='*') // it can be a star
                adj[i][j] = impossible;  //defined number
            else {
                temp=atoi(s);
                inrange(temp,0,20,"distance");  //checking if it is in range
                adj[i][j]=temp;     //saving to the adjacency matrix
            }
            s[0]='\0';
            if(j != noc-1){     // if it is not the last element i am expecting a space after it
                scanf("%[ ]",s);
                more_than_one_space(s); // should be only one space no more than that
                s[0]='\0';
            }

        }
        if(i != noc-1){ // if not the last row i am expecting a new line
        scanf("%[\n]",s);
            if (strlen(s)!= 1)  // should be no empty line between them
            {
                printf("Invalid structure");
                exit(1);
            }
            s[0]='\0';
        }
    }
    if(!(fgetc(stdin)==EOF)) // there should reach the end of file if not there is a problem in the input file
    {
        printf("Invalid structure");
        exit(1);
    }

    /////////////////////////////////////////////
    //the adjacency matrix has been read successfully now we need to do the algorithmic part
    //now printing everything

    dijkstra(adj, in, d);
    printf("The shortest path is %d.\n", dist[d]);
    cntPaths(in);
    printf("The number of shortest paths is %d:\n", number_of_paths);
    number_of_paths = 1;
    memset(visited, sizeof(visited), 0);
    printPaths(in);

    return 0;
}