116 - Unidirectional TSP

BJM · Post by **BJM** » Sat Oct 15, 2005 11:26 pm

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

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 · Post by **tan_Yui** » Mon Oct 17, 2005 3:47 am

BJM, thank you very much for your help !

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 · Post by **lovemagic** » Mon Dec 05, 2005 6:40 pm

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;
}

lovemagic · Post by **lovemagic** » Wed Dec 07, 2005 6:31 pm

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.....

mamun · Post by **mamun** » Fri Dec 09, 2005 6:43 pm

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 · Post by **emotional blind** » Sat Dec 10, 2005 6:26 am

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 · Post by **emotional blind** » Sat Dec 10, 2005 6:27 am

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 · Post by **lovemagic** » Sun Dec 11, 2005 2:16 am

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.

feryll · Post by **feryll** » Sat Jan 07, 2006 4:57 am

#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 · Post by **xavier1214** » Wed Jan 18, 2006 6:09 pm

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 · Post by **tan_Yui** » Thu Jan 19, 2006 12:46 pm

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 · Post by **xavier1214** » Thu Jan 19, 2006 2:09 pm

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 · Post by **Beenuxers** » Wed May 10, 2006 4:31 am

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 · Post by **emotional blind** » Wed May 10, 2006 1:20 pm

think about DP approach,
backtrack is slower

Beenuxers · Post by **Beenuxers** » Thu May 11, 2006 4:58 am

Hi Arif, thx for ur reply...

Yup, u rite on it... But, could you give me some samples of the dp approach?

Because, i still can't figure it out...

OJ Board

116 - Unidirectional TSP

116: where's my wrong?

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

116 WA, plz help, had tried test data

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

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