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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
