shortestpaths

Shortest Paths with Multiplicative Cost. In a given undirected graph, the path cost is measured as a

Shortest Paths with Multiplicative Cost. In a given undirected graph, the path cost is measured as a product
 of all the edges in the path. The weights are rational numbers (e.g., 0.25, 0.75, 3.75 etc) or integers 
 (2, 3). There are no negative edges. Given such a graph as input, you are to output the shortest path between any two given vertices. Input is the adjacency matrix and the two vertices. You must output the path.
Input:
4
0 0.2 0.3 0
0.2 0 0.1 0.2
0.3 0.1 0 0.5
0 0.2 0.5 0
1 4
Output:
1->2->3->4

solution
#include<stdio.h>
#include<stdlib.h>

struct Stk
{
int* q;
int top;
};

struct Node
{
int sz;
float cost;
struct Stk *st;
struct Node *next;
};

struct Stk *st=NULL;
struct Node *nd = NULL;
struct Node *head = NULL;

void push(int i, int n)
{
/*printf("inside push %d \n",i);*/
if(isempty()==-1)
{
st->q= (int*)malloc(sizeof(int)*n);

}
st->top++;
st->q[st->top]=i;
}

int pop()
{

int res;
/*printf("inside pop ");;*/
if(isempty()==-1)
{
return -1;
}
res = st->q[st->top];
/*printf("%d\n",res);*/
st->top--;
return res;

}

int isempty()
{
if(st->top==-1)
return -1;
else
return 0;
}

void copyStk(struct Stk* t, struct Stk* st, int n)
{
int i;
/*printf("inside copystk\n");*/


t->q = (int*)malloc(sizeof(int)*n);
for(i=0;i<=st->top;i++)
{
t->q[i]=st->q[i];
}
t->top= st->top;
/*printf("t->top is %d\n",t->top);*/
}
void printq(int n, float cost )
{
int i,setval,cnt;
struct Node* nd1;
struct Node* prev;

prev= NULL;
nd1=NULL;

setval=0;

if (nd==NULL)
{
/*printf("inside if printq\n");*/
nd=(struct Node*)malloc(sizeof(struct Node));
head = nd;
/*printf("st->top is %d\n",st->top);*/
nd->cost = cost;

nd->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd->st,st,n);

/*printf("nd->st->top is %d\n",nd->st->top);*/
}
else
{
/*printf("inside else printq\n");*/
nd = head;

/*printf("cnt is %d\n",cnt);*/
prev = head;
while(nd != NULL)
{
/*printf("cost is %f, and nd->cost is %f\n",cost,nd->cost);*/
if(cost < nd->cost)
{
nd1 = (struct Node*)malloc(sizeof(struct Node));
nd1->cost = cost;
/*printf("st->top is %d\n",st->top);*/

nd1->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd1->st,st,n);
nd1->next = nd;

if(head==nd)
head = nd1;
else
prev->next=nd1;

setval=1;
break;
}
if(cost>=nd->cost)
{
prev=nd;
nd = nd->next;
}
}

if(setval==0)
{

nd1 = (struct Node*)malloc(sizeof(struct Node));
nd1->cost = cost;


nd1->st = (struct Stk*)malloc(sizeof(struct Stk));
copyStk(nd1->st,st,n);
prev->next=nd1;
}


}


}

/*void reset(int arr[][3],int n)*/
void reset(float** arr,int n)
{
int i,j;
i=j=0;
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(arr[i][j]==-1)
arr[i][j]=1;
}

}
free(st->q);
st->top=-1;
head=NULL;
nd = NULL;
}

/*int dfs(int src,int dest, int arr[][3], int n, int cnt)*/
int dfs(int src,int dest, float** arr, int n, float cnt)
{
int i,setval;
float cnt1,val=0.0;
setval=-1;
/*printf("inside dfs, 1: cost is %f, src is %d\n",cnt,src);*/
for(i=0;i<n;i++)
{

if(arr[src][i]>0)
{
push(i,n);

val = arr[src][i];
/*printf("inside dfs, val is %f\n",val);*/
arr[src][i]=-arr[src][i];
arr[i][src]= -arr[i][src];
if(cnt==0.0)
{
cnt = val;
setval=0;
}
else
{
cnt = cnt*val;
setval=1;
}


if(i==dest)
{
/*printf("inside dfs, 2f: i is %d, cost is %f\n", i,cnt);*/
printq(n,cnt);
}
else
cnt1 = dfs(i,dest,arr,n,cnt);
if(setval==0)
{
cnt=cnt-val;
setval=-1;
}
else
{
cnt = cnt/val;
setval=-1;
}
pop();
}
}

return cnt;


}

int main()
{
int notestcases;
int src,dest, i,j,n,cnt;
float** arr;
int* srcArr;
int* destArr;
/*int arr[][3] = {{0,1,1},{0,0,1},{0,0,0}};*/
i=0;j=0;

st= (struct Stk *)malloc(sizeof(struct Stk));
st->top=-1;

scanf("%d",&n);
getchar();
if(n > 0)
{
arr = (float**) malloc(sizeof(float*)*(n));


for(i=0;i<n+1;i++)
arr[i]=(float*)malloc(sizeof(float)*(n));


for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{

scanf("%f",&arr[i][j]);

}

}


scanf("%d%d",&src,&dest);

i=0;



src--;dest--;
if (src == dest)
{
printf("%d\n",src+1);
return 0;
}
push(src,n);
cnt  = dfs(src,dest,arr,n,0.0);


nd = head;
if(nd != NULL)
{

for(i=0;i<=nd->st->top;i++)
{
printf("%d",(nd->st->q[i])+1);
if(i < nd->st->top)
printf("->");
}
printf("\n");


}


/*reset(arr,n);*/



/*if notestcases>0*/
}/*if n>0*/

return 0;
}