## 116 - Unidirectional TSP

Moderator: Board moderators

BJM
New poster
Posts: 7
Joined: Sat Nov 16, 2002 3:28 pm
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
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
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 am

### 116: where's my wrong?

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

mamun
A great helper
Posts: 286
Joined: Mon Oct 03, 2005 1:54 pm
Contact:
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
Contact:
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
``````

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

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:
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
``````

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

lovemagic
Learning poster
Posts: 52
Joined: Thu Oct 02, 2003 11:38 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.
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.

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

typedef int ITEM;

struct node
{
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;
delete tmp;
}
scount=0;
}

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

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

ITEM ret=top->item;
node* tmp=top;
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

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

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
Hi, tan_Yui.
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

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