116 - Unidirectional TSP

All about problems in Volume 1. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

BJM
New poster
Posts: 7
Joined: Sat Nov 16, 2002 3:28 pm

Post by BJM »

Looks like a hang-over problem to me. Try:

Code: Select all

4 29
1 -1 0 0 1 -1 -1 -1 1 1 0 1 -1 -1 -1 0 -1 -1 1 -1 1 0 0 -1 0 -1 1 1 0
-1 1 0 -1 -1 0 1 0 -1 -1 -1 -1 1 1 0 -1 -1 0 -1 -1 1 -1 1 0 -1 1 0 1 -1
0 0 1 0 -1 1 0 0 1 1 0 -1 1 1 -1 -1 1 0 0 1 1 0 -1 1 0 -1 -1 1 1
1 -1 -1 -1 -1 -1 0 0 0 1 -1 0 0 0 -1 -1 0 -1 0 1 0 -1 1 0 1 1 -1 0 1
1 11
-1 0 0 -1 1 1 1 -1 1 -1 1
BJM

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Post by tan_Yui »

BJM, thank you very much for your help ! :D
My code didn't have the condition if m==1 , so I failed your 2nd input.
After I added the condition, I could get Accepted !

Best regards.

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

116: where's my wrong?

Post by lovemagic »

I got several wa in this prob though all the test cases i found in the board outputs same for my code.Smbody help me?

Code: Select all


#include <stdio.h>
long long A[15][105],M[15][105],mark[15][105];
long long m,n,min;

long long min_val(long long a,long long b,long long c){
    if(a<=c){
        if(a<=b)return a;
        else return b;
    }
    else{
        if(c<b)return c;
        else return b;
    }           
}  

void init(){
    long long i,j;
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            M[i][j]=mark[i][j]=0;
}      

int main(){
//    freopen("c:\\101.in","rt",stdin);
//    freopen("c:\\101.out","wt",stdout);
    long long i,j,f,tmp;
    long long a,b,c;
    while(scanf("%lld %lld",&m,&n)==2){
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                scanf("%lld",&A[i][j]);
        init();

        for(i=0;i<m;i++)
            M[i][n-1]=A[i][n-1];

        for(j=n-2;j>=0;j--)
            for(i=0;i<m;i++){
                a=(i+m-1)%m;b=i;c=(i+1)%m;
                if(a>b){
                    tmp=a;a=b;b=tmp;    
                }
                if(a>c){
                    tmp=a;a=c;c=tmp;    
                }
                if(b>c){
                    tmp=b;b=c;c=tmp;    
                }    
                M[i][j]=A[i][j]+min_val(M[a][j+1],M[b][j+1],M[c][j+1]);
                if(M[i][j]==A[i][j]+M[a][j+1])mark[i][j]=a;
                else if(M[i][j]==A[i][j]+M[b][j+1])mark[i][j]=b;
                else if(M[i][j]==A[i][j]+M[c][j+1])mark[i][j]=c;
            }    

        min=M[0][0];
        for(i=1;i<m;i++)
            if(M[i][0]<min)
                min=M[i][0];
         
           
        for(i=0;i<m;i++){
            if(M[i][0]==min){
                printf("%lld",i+1);
                i=mark[i][0];
                break;         
            }    
        }  
        
        for(j=0;j<=n-2;j++){
            printf(" %lld",mark[i][j]+1);
            i=mark[i][j];                
        } 
        printf("\n");        
        printf("%lld\n",min);                     
    }    
    return 0;
}

khobaib

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic »

plz reply cz i see no wrong in my code.I m waiting for smbody who can help me by posting sm critical i/o or debugging my code..... :cry:
khobaib

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Location: Bangladesh
Contact:

Post by mamun »

Oh! my goodness! So many hours I wasted (or used) for this. There are already so many posts about this problem and so many nice sample I/O. Believe me, my WA output matches all of them! Now how can I help myself?

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

to love magic
try this input

Code: Select all

4 7 
1 2 -3 4 -2 1 5 
-1 3 5 -2 6 -3 4 
2 1 3 -2 -1 3 1 
3 -3 4 2 -3 4 3 
your output

Code: Select all

1 1 4 1 2 1 4
21
but correct output should be

Code: Select all

1 1 4 1 2 1 4
21
buy

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

to love magic
try this input

Code: Select all

4 7 
1 2 -3 4 -2 1 5 
-1 3 5 -2 6 -3 4 
2 1 3 -2 -1 3 1 
3 -3 4 2 -3 4 3 
your output

Code: Select all

1 1 4 1 2 1 4
21
but correct output should be

Code: Select all

1 4 1 2 1 2 3
-11
buy

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

Post by lovemagic »

possibly u compiler doesnt support long long data type.So it gives that answer.my edited code (the only change is all long long is changed into int so that it can be compiled in any c++ version) gives the same ans as urs.

Code: Select all


#include <stdio.h>
int A[15][105],M[15][105],mark[15][105];
int m,n,min;

int min_val(int a,int b,int c){
    if(a<=c){
        if(a<=b)return a;
        else return b;
    }
    else{
        if(c<b)return c;
        else return b;
    }           
}  

void init(){
    int i,j;
    for(i=0;i<m;i++)
        for(j=0;j<n;j++)
            M[i][j]=mark[i][j]=0;
}      

int main(){
    int i,j,f,tmp;
    int a,b,c;
    while(scanf("%d %d",&m,&n)==2){
        for(i=0;i<m;i++)
            for(j=0;j<n;j++)
                scanf("%d",&A[i][j]);
        init();

        for(i=0;i<m;i++)
            M[i][n-1]=A[i][n-1];

        for(j=n-2;j>=0;j--)
            for(i=0;i<m;i++){
                a=(i+m-1)%m;b=i;c=(i+1)%m;
                if(a>b){
                    tmp=a;a=b;b=tmp;    
                }
                if(a>c){
                    tmp=a;a=c;c=tmp;    
                }
                if(b>c){
                    tmp=b;b=c;c=tmp;    
                }    
                M[i][j]=A[i][j]+min_val(M[a][j+1],M[b][j+1],M[c][j+1]);
                if(M[i][j]==A[i][j]+M[a][j+1])mark[i][j]=a;
                else if(M[i][j]==A[i][j]+M[b][j+1])mark[i][j]=b;
                else if(M[i][j]==A[i][j]+M[c][j+1])mark[i][j]=c;
            }    

        min=M[0][0];
        for(i=1;i<m;i++)
            if(M[i][0]<min)
                min=M[i][0];         
           
        for(i=0;i<m;i++){
            if(M[i][0]==min){
                printf("%d",i+1);
                i=mark[i][0];
                break;         
            }    
        } 
        
        for(j=0;j<=n-2;j++){
            printf(" %d",mark[i][j]+1);
            i=mark[i][j];                
        } 
        printf("\n");                   
        printf("%d\n",min);                   
    }    
    return 0;
}

so u see,there is wrong may be in other place.
khobaib

feryll
New poster
Posts: 1
Joined: Sat Jan 07, 2006 4:52 am

116 plz. help me to find the logical error in this code.

Post by feryll »

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

typedef int ITEM;

struct node
{
node* link;
ITEM item;
};

class Cstack
{
public:
node *top;
node *tail;
int scount;
Cstack()
{
scount=0;
top=NULL;
}

~Cstack()
{
del();
}

void del()
{
node *tmp;
while(top)
{
tmp=top;
top=top->link;
delete tmp;
}
scount=0;
}

void push(ITEM item)
{
node *tmp=new node;
tmp->item=item;
tmp->link=NULL;
if(top) tmp->link=top;
top=tmp;
scount++;
}

ITEM pop()
{
if(scount==0) return -1;

ITEM ret=top->item;
node* tmp=top;
top=top->link;
delete tmp;
scount--;
return ret;
}
};

int prevMin(int col,int x, int y, int **mat)
{
int ret=(x-1)<0 ? col-1:x-1;
if(mat[ret][y-1]>mat[x][y-1]) ret=x;
else if(mat[ret][y-1]==mat[x][y-1]) ret= ret<x ? ret:x;
if(mat[ret][y-1]>mat[(x+1)%col][y-1]) ret=(x+1)%col;
else if(mat[ret][y-1]==mat[(x+1)%col][y-1]) ret= ret<(x+1)%col ? ret:(x+1)%col;
return ret;
}

int uTSP(int col, int row, int **mat)
{
int i,j,ret;
Cstack s;

for(j=1;j<row;j++)
{
for(i=0;i<col;i++) mat[j]+=mat[prevMin(col,i,j,mat)][j-1];
}

ret=0;
for(i=1;i<col;i++) if(mat[ret][row-1]>mat[row-1]) ret=i;
j=ret;
for(i=row-1;i>=0;i--)
{
s.push(j);
j=prevMin(col,j,i,mat);
}

while(s.scount) printf("%d ",s.pop()+1);
printf("\n");

return mat[ret][row-1];
}

int main()
{
int **mat;
int col,row,i,j,ret;
while(1)
{
ret=scanf("%d %d",&col,&row);
if(ret==EOF) break;
mat = (int**) malloc(sizeof(int*)*(col));
for(i=0;i<col;i++)
{
mat = (int*) malloc(sizeof(int)*row);
for(j=0;j<row;j++) scanf("%d",&mat[j]);
}
printf("%d\n",uTSP(col,row,mat));

for(i=0;i<col;i++) free(mat);
free(mat);
}
return 0;
}

xavier1214
New poster
Posts: 2
Joined: Wed Jan 18, 2006 5:58 pm

116 WA, plz help, had tried test data

Post by xavier1214 »

Here is my code...

Code: Select all

//116

#include <iostream>
using namespace std;

int value[10][100];
int sum[10][100][2];
short int way[100];
int row, column, i, j, a, b, c, min, nextcolumn, index;

void main()
{
	while(cin>>row>>column)
	{
		for(i=0;i<row;i++)
			for(j=0;j<column;j++)
				cin>>value[i][j];
		for(i=0;i<row;i++)
			sum[i][column-1][0]=value[i][column-1];
		for(j=column-2;j>=0;j--)
		{
			nextcolumn=j+1;
			for(i=0;i<row;i++)
			{
				if(i==0)
				{
					a=0;
					b=1;
					c=row-1;
				}
				else if(i==row-1)
				{
					a=0;
					b=row-2;
					c=row-1;
				}
				else
				{
					a=i-1;
					b=i;
					c=i+1;
				}
				index=a;
				min=sum[a][nextcolumn][0];
				if(min>sum[b][nextcolumn][0])
				{
					min=sum[b][nextcolumn][0];
					index=b;
				}
				if(min>sum[c][nextcolumn][0])
				{
					min=sum[c][nextcolumn][0];
					index=c;
				}
				
				sum[i][j][0]=min+value[i][j];
				sum[i][j][1]=index;
			}
		}

		min=sum[0][0][0];
		index=0;
		for(i=1;i<row;i++)
		{
			if(sum[i][0][0]<min)
			{
				min=sum[i][0][0];
				index=i;
			}
		}

		way[0]=index;
		for(i=0;i<column-1;i++)
		{
			index=sum[index][i][1];
			way[i+1]=index;
		}

		for(i=0;i<column;i++)
			cout<<way[i]+1<<" ";
		cout<<"\n"<<min<<endl;
	}
}
Here is the testing data
6 6
1 2 2 1 2 1
2 1 2 2 1 2
2 2 1 2 2 1
1 2 2 1 2 2
2 1 2 2 1 2
2 2 1 2 2 1

6 8
9 1 9 9 1 1 1 1
1 9 9 1 9 9 9 9
9 9 1 9 9 1 1 1
1 1 9 9 1 9 9 9
9 9 9 1 9 9 9 9
9 9 1 9 9 9 9 9

6 7
1 9 9 1 9 9 9
9 1 1 9 9 9 9
9 9 9 9 1 1 1
9 9 9 1 9 9 9
9 9 1 9 9 9 9
9 1 9 9 1 1 1

4 4
3 3 3 3
3 3 3 3
3 3 3 1
1 1 1 1

4 4
3 3 3 1
3 3 3 3
3 3 3 1
1 1 1 1

4 4
3 3
3 1 3 3 3
3 3 3 3 1 1
1 1 1

4 6
1 1 1 3 3 1
3 3 3 1 3 1
1 1 1 1 1 3
3 3 3 3 1 1

10 10
9 0 9 9 9 9 9 9 9 9
9 9 0 9 2 2 1 1 1 1
9 9 9 2 9 9 9 9 9 9
1 1 1 1 9 9 9 9 9 9
9 9 9 9 1 1 1 1 1 1
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
9 9 9 9 9 9 9 9 9 9
0 9 9 9 9 9 9 9 9 9

10 16
0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 0
0 1 1 1 1 0 1 1 1 1 1 0 1 1 0 1
1 0 0 0 0 1 1 1 1 1 0 1 0 0 1 1
1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1
0 1 1 0 1 1 1 1 0 1 0 1 1 1 1 0
1 1 1 1 0 0 1 0 1 1 1 0 0 0 0 1
1 1 1 1 1 1 0 1 0 1 1 1 1 0 1 1
1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 0
1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1
1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1

4 7
1 2 -3 4 -2 1 5
-1 3 5 -2 6 -3 4
2 1 3 -2 -1 3 1
3 -3 4 2 -3 4 3

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3

2 2
9 10
9 10

5 6
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5

3 4
1 2 3 4
1 2 3 4
1 2 3 4

5 5
1 5 10 6 3
5 1 8 4 11
10 12 5 2 9
7 3 20 5 8
4 1 5 12 6

5 10
11 53 34 73 18 53 99 52 31 54
4 72 24 6 46 17 63 82 89 25
67 22 10 97 99 64 33 45 81 76
24 71 46 62 18 11 54 40 17 51
99 8 57 76 7 51 90 92 51 21

5 10
11 53 1 73 18 53 99 52 31 54
4 72 54 6 46 17 63 82 89 25
67 22 80 97 99 64 33 45 81 76
24 71 46 62 18 11 54 40 17 51
99 8 57 76 7 51 90 92 51 21

5 6
-3 -4 -1 -2 -8 -6
-6 -1 -8 -2 -7 -4 -5 -9 -3 -9 -9 -5
-8 -4 -1 -3 -2 -6 -3 -7 -2 -8 -6 -4

10 100
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

10 9
2 1 2 1 1 1 1 1 2
1 2 1 2 1 2 1 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
2 2 2 2 2 2 2 2 2
1 2 1 2 1 2 1 2 2

4 7
1 2 -3 4 -2 1 5
-1 3 5 -2 6 -3 4
2 1 3 -2 -1 3 1
3 -3 4 2 -3 4 3

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 8 6 4

5 6
3 4 1 2 8 6
6 1 8 2 7 4
5 9 3 9 9 5
8 4 1 3 2 6
3 7 2 1 2 3

5 6
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5

10 1
2 3 4 5 6 -1 29 19 -10 19

1 10
-1 -1 -1 -1 -1 -1 -1 -1 1 1

Here is the result
1 2 3 4 5 6
6

2 1 6 5 4 3 3 3
8

1 2 2 1 6 6 6
7

4 4 4 3
4

4 4 4 1
4

4 4 4 1
4

1 1 1 2 3 2
6

4 4 4 4 5 5 5 5 5 5
10

2 3 3 3 3 2 1 10 9 8 8 8 8 7 6 5
0

1 4 1 2 1 2 3
-11

1 2 3 4 4 5
16

1 2 1 5 4 5
11

1 1
19

1 1 1 1 1 1
6

1 1 1 1
10

1 2 3 2 1
14

2 3 3 2 1 2 3 4 4 5
188

1 5 1 2 1 2 3 4 4 5
172

4 3 2 3 3 4
-49

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
100

2 1 2 1 1 1 1 1 1
10

1 4 1 2 1 2 3
-11

1 2 3 4 4 5
16

1 2 1 5 4 5
11

1 1 1 1 1 1
6

9
-10

1 1 1 1 1 1 1 1 1 1
-6


plz somebody tell me where the problem is, thx

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 116 WA, plz help, had tried test data

Post by tan_Yui »

Hi, xavier1214.
Try the following input.

1 11
-1 0 0 -1 1 1 1 -1 1 -1 1

Output is :
1 1 1 1 1 1 1 1 1 1 1
1

By the way, your output set are same as mine, except for one input.
Input '10 100 ....' has more than 10*100 elements, so my code couldn't execute.

Best regards.

xavier1214
New poster
Posts: 2
Joined: Wed Jan 18, 2006 5:58 pm

Post by xavier1214 »

Hi, tan_Yui.
Really thx your help, or I had decided to skip the problem already.
This testing data really help me realize where the problem is.

b.t.w. input '10 100...' must be the copy-paste error, never mind.

best regard...

Beenuxers
New poster
Posts: 6
Joined: Mon Mar 13, 2006 6:29 am
Location: Jakarta
Contact:

116 TLE... Plz help.... :(... 2x TLE

Post by Beenuxers »

Can anyone help me to make it faster? I still have no idea how to store the lexicographically path efficiently.... I'm waiting for ur answer.... Thx... :)..
#include <stdio.h>
#include <math.h>

int cost[10][100], output[10][100];
int idx, num;
long min;

void lexico(int temp[100], int output[100], int n)
{
for(int i=0;i<n;i++)
if(temp<output)
output= temp;
}

void copyArr(int temp[100], int output[100], int n)
{
for(int i=0;i<n;i++)
output= temp;
}

void findMin(int row, int strow, int stcol, int bil[10][100], int temp[100], int n)
{
temp[stcol]= strow;
if(stcol==n-1) {
if(min>=cost[strow][stcol]) {
if(min>cost[strow][stcol]) {
num= idx;
copyArr(temp,output[idx],n);
}
else
lexico(temp,output[idx],n);

min= cost[strow][stcol];
}
return ;
}

int next;

next= strow-1;
if(next<0) next= row-1;
if(cost[strow][stcol]+bil[next][stcol+1] < cost[next][stcol+1]) {
cost[next][stcol+1]= cost[strow][stcol]+bil[next][stcol+1];
findMin(row,next,stcol+1,bil,temp,n);
}

next= strow;
if(cost[strow][stcol]+bil[next][stcol+1] < cost[next][stcol+1]) {
cost[next][stcol+1]= cost[strow][stcol]+bil[next][stcol+1];
findMin(row,next,stcol+1,bil,temp,n);
}

next= strow+1;
if(next==row) next= 0;
if(cost[strow][stcol]+bil[next][stcol+1] < cost[next][stcol+1]) {
cost[next][stcol+1]= cost[strow][stcol]+bil[next][stcol+1];
findMin(row,next,stcol+1,bil,temp,n);
}
}

main()
{
int row, col, i, j;
int bil[10][100], temp[100];

#ifndef ONLINE_JUDGE
freopen("116.in","r",stdin);
freopen("116.out","w",stdout);
#endif

while(scanf("%d%d", &row, &col)==2) {
for(i=0;i<row;i++) {
for(j=0;j<col;j++) {
scanf("%d", &bil[j]);
cost[j]= pow(2,31)-1;
}
cost[0]= bil[0];
}

min= pow(2,31)-1;
for(idx=0;idx<row;idx++)
findMin(row,idx,0,bil,temp,col);

for(i=0;i<col;i++) printf("%d ", output[num][i]+1);
putchar('\n');
printf("%ld \n", min);
}
}
[/quote]

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind »

think about DP approach,
backtrack is slower

Beenuxers
New poster
Posts: 6
Joined: Mon Mar 13, 2006 6:29 am
Location: Jakarta
Contact:

Post by Beenuxers »

Hi Arif, thx for ur reply... :wink:
Yup, u rite on it... But, could you give me some samples of the dp approach? :wink: Because, i still can't figure it out... :-?

Post Reply

Return to “Volume 1 (100-199)”