well mukesh , I solved the problem iteratively from right to left and filling up an arry. Here is my code. I think Lago Haryanto was right. you have to select and find out the lexicographically shortest path greedily.
Minhaz code: /* @JUDGE_ID: 55890 116 C++*/ #include<stdio.h> void min3(int,int); void dp(void); void print(void); struct datum{ long long cur_val; long long cur_sum; int nextro; }; struct datum data[11][101]; int cur_ro,cur_col; void main(){ int i,j; while(scanf("%d",&cur_ro)==1){ scanf("%d",&cur_col); for(i=1;i<=cur_ro;i++){ for(j=1;j<=cur_col;j++){ scanf("%lld",&data[i][j].cur_val); } } dp(); print(); } } void dp(void){ int i,j; for(i=1;i<=cur_ro;i++) data[i][cur_col].cur_sum=data[i][cur_col].cur_val; for(j=cur_col-1;j>0;j--){ for(i=1;i<=cur_ro;i++){ min3(i,j); } } } void min3(int row,int col){ int a,b,c; long long sum_a,sum_b,sum_c; b=row; sum_b=data[row][col+1].cur_sum; a=row-1; c=row+1; if(row==1) a=cur_ro; if(row==cur_ro) c=1; sum_a=data[a][col+1].cur_sum; sum_c=data[c][col+1].cur_sum; if(sum_a<sum_b){ if(sum_a<sum_c){ data[row][col].nextro=a; data[row][col].cur_sum=sum_a+data[row][col].cur_val; } else if(sum_a==sum_c){ if(a<c){ data[row][col].nextro=a; data[row][col].cur_sum=sum_a+data[row][col].cur_val; } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else if(sum_a==sum_b){ if(a<b){ if(sum_a<sum_c){ data[row][col].nextro=a; data[row][col].cur_sum=sum_a+data[row][col].cur_val; } else if(sum_a==sum_c){ if(a<c){ data[row][col].nextro=a; data[row][col].cur_sum=sum_a+data[row][col].cur_val; } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ if(sum_b<sum_c){ data[row][col].nextro=b; data[row][col].cur_sum=sum_b+data[row][col].cur_val; } else if(sum_b==sum_c){ if(b<c){ data[row][col].nextro=b; data[row][col].cur_sum=sum_b+data[row][col].cur_val; } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } } else{ if(sum_b<sum_c){ data[row][col].nextro=b; data[row][col].cur_sum=sum_b+data[row][col].cur_val; } else if(sum_b==sum_c){ if(b<c){ data[row][col].nextro=b; data[row][col].cur_sum=sum_b+data[row][col].cur_val; } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } else{ data[row][col].nextro=c; data[row][col].cur_sum=sum_c+data[row][col].cur_val; } } } void print(void){ int min_ro,i; long long min_sum; if(cur_ro!=0) min_ro=1; else min_ro=0; if(cur_col!=0) min_sum=data[1][1].cur_sum; else min_sum=0; for(i=2;i<=cur_ro;i++){ if(min_sum>data[i][1].cur_sum){ min_sum=data[i][1].cur_sum; min_ro=i; } } printf("%d",min_ro); for(i=1;i<cur_col;i++){ min_ro=data[min_ro][i].nextro; printf(" %d",min_ro); } printf("\n%lld\n",min_sum); } On 12/13/06, mukesh tiwari <[EMAIL PROTECTED]> wrote: > > > hi Lego Haryanto > i tried ur metoh but still not working ...here is my code and i m > tired with this program . i am not getting even a single method to find > lexicographic shortest path. > > > #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,v1; > 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; > //printf("min=%d arr[%d]=%d\n",min2,n-1,arr[n-1]); > for(j=n-2;j>=0;j--) > { > //printf("j=%d ",j); > min=m1[(arr[j+1]+m-1)%m][j]; > t1=(arr[j+1]+m-1)%m; > t=t1; > if(min>m1[arr[j+1]][j]) > { > min=m1[arr[j+1]][j]; > t2=arr[j+1]; > t=t2; > } > else if(min==m1[arr[j+1]][j]) > { > t2=arr[j+1]; > if(t1>t2) > t=t2; > else > t=t1; > } > > if(min>m1[(arr[j+1]+1)%m][j]) > { > min=m1[(arr[j+1]+1)%m][j]; > t3=(arr[j+1]+1)%m; > t=t3; > > } > > else if(min==m1[(arr[j+1]+1)%m][j]) > { > t3=(arr[j+1]+1)%m; > if(t>t3) > t=t3; > } > 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 -~----------~----~----~----~------~----~------~--~---