hi friends i am try to solving this question
http://online-judge.uva.es/p/v1/116.html
for this problem i use left to right dynamic programming so i m getting the
total minimum cost but i m not getting how to find out lexicographically
shortest path .here is my code .....if u can change it fine but plz suggest
me algorithm to find lexicographically shortest path.
my program works fine if one path exist but if more than one path exist then
it's not giving lexicographically smallest path.what i m doing is
i m finding last column(n-1) minimum value and note down the row number (let
it be i).now in second last column(n-2) i searched out minmium value in row
i-1,i and i+1 becoz of problem property. and i keep doing this until i reach
the 0th column.doing this i m not getting what i suppose to find out
...lexicographically smallest path.plz help...
#include<stdio.h>
int min1(int k,int m,int n)
{
int min;
min=k;
if(min>m)
min=m;
if(min>n)
min=n;
return(min);
}
main()
{
int m1[100][100],a[100][100],i,j,m,n,min,k,arr[100],t,min2,t1,t2,t3;
while(scanf("%d%d",&m,&n)==2)
{
for(i=0;i<m;i++)
for(j=0;j<n;j++)
scanf("%d",&a[i][j]);
for(i=0;i<m;i++)
m1[i][0]=a[i][0];
for(j=1;j<n;j++)
for(i=0;i<m;i++)
m1[i][j]=a[i][j]+min1(m1[(i+m-1)%m][j-1],m1[i][j-1],m1[(i+1)%m][j-1]);
/*for(i=0;i<m;i++)
{
for(j=0;j<n;j++)
printf("%d ",m1[i][j]);
printf("\n");
}*/
//printf("\n");
min2=m1[0][n-1];
k=0;
for(i=1;i<m;i++)
if(m1[i][n-1]<min2)
{
min2=m1[i][n-1];
k=i;
}
//printf("k=%d min=%d\n",k+1,min2);
arr[n-1]=k;
for(j=n-2;j>=0;j--)
{
min=m1[(arr[j+1]+m-1)%m][j];
t=(arr[j+1]+m-1)%m;
if(min>m1[arr[j+1]][j])
{
min=m1[arr[j+1]][j];
t=arr[j+1];
}
if(min>m1[(arr[j+1]+1)%m][j])
{
min=m1[(arr[j+1]+1)%m][j];
t=(arr[j+1]+1)%m;
}
arr[j]=t;
//printf("min=%d arr[%d]=%d\n",min,j,t);
}
for(i=0;i<=n-1;i++)
printf("%d ",arr[i]+1);
printf("\n%d\n",min2);
}
}
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
