## 116 - Unidirectional TSP

Moderator: Board moderators

wsarzynski
New poster
Posts: 19
Joined: Fri Oct 04, 2002 7:50 pm
Location: Warsaw, Poland
Is lex smallest path the one with smallest row index in
previous column ?
Can i go from row with max index to row 0 ?
Maybe come traps in input, some chars to ignore or
no spaces between ints ?

Robbie
New poster
Posts: 15
Joined: Wed Aug 07, 2002 11:38 am
Location: Viet Nam

### Need helps !!!

Here is it :

Program Pr_116;

const maxm =11;
maxn =101;
max =2147483647;
fi ='116.txt';
fo ='116.out';

type m1 =array[1..maxm,1..maxn]of longint;
m2 =array[1..maxm,1..maxn]of integer;

var a,l :m1;
m,n :longint;
test :longint;
min :longint;

var i,j :longint;
begin

for i:=1 to m do
for j:=1 to n do read(a[i,j]);
end;

Procedure Process;
var i,j,u,k,li :integer;
pre :m2;
begin
fillchar(pre,sizeof(pre),0);

for i:=1 to m do
for j:=1 to n do
if j=n then l[i,j]:=a[i,j]
else l[i,j]:=max;

for j:=n downto 2 do
for i:=1 to m do
for k:=i-1 to i+1 do
begin
u:=k;
if u=0 then u:=m;
if u=m+1 then u:=1 ;

if l[u,j-1]>l[i,j]+a[u,j-1] then
begin
l[u,j-1]:=l[i,j]+a[u,j-1];
pre[u,j-1]:=i;
end
else if (l[u,j-1]=l[i,j]+a[u,j-1]) and (pre[u,j-1]>i) then
begin
pre[u,j-1]:=i;
end;
end;

min:=max ; li:=0;
for i:=1 to m do
if l[i,1]<min then
begin
min:=l[i,1] ;
li:=i;
end
else if l[i,1]=min then
if li=0 then li:=i;

write(li);
for j:=1 to n-1 do
begin
write(' ',pre[li,j]);
li:=pre[li,j];
end;
writeln;
write(min);
end;

Begin
{Assign(input,fi); reset(input);
Assign(output,fo); rewrite(output);}

test:=0;
while not eof(input) do
begin

if (m=0) and (n=0) then break;
inc(test);
if test>1 then writeln;
Process ;
end;

{ close(output);
close(input);}
end.[/pascal][/code]

vcm
New poster
Posts: 1
Joined: Thu Oct 31, 2002 3:00 pm

### 116 unidirectional tsp help!

Hi there,
can any one help me ?
i don't know why this code always gives me wrong answer.
I used dynamic programming, an used long int, and i have tested with some more cases (random cases)
Thanks!

[cpp]
/* #: 116
* Title: Unidirectional TSP
* Technique: dynamic programming
*/
#include <iostream.h>
#include <algorithm>
using namespace std;
typedef unsigned short idx;
typedef long myint;

const short MAXN = 110;
const short MAXM = 110;

myint table [MAXN][MAXM];
idx nn, mm;

{
if (cin.eof ()) return false;
cin >> nn >> mm;
if (cin.eof ()) return false;
idx j,i;
// reads the table in inverse and transpose form
for (j=0; j<nn; j++) {
for (i=0; i<mm; i++) {
cin >> table [mm-i-1][j];
if (cin.eof ()) return false;
}
}
return true;
}
void printTable ()
{
idx j, i;
for (j=0; j<mm; j++) {
for (i=0; i<nn; i++) {
cout << table [j] << " ";
}
cout <<endl;
}
}
idx getNext (idx i)
{
if (i==(nn-1))
return 0;
return i+1;
}
idx getPrev (idx i)
{
if (i==0)
return nn-1;
return i-1;
}
idx min2 (myint* vv, idx i, idx j)
{
if (vv == vv [j])
return i<j?i:j;
return vv <vv [j]?i:j;
}
idx min3 (myint* vv, idx i)
{
return min2 ( vv, min2 (vv,getPrev (i),i), getNext (i) );
}
void print (myint* vv)
{
idx i;
for (i=0; i<nn; i++)
cout << vv << " ";
cout <<endl;
}
void getMinCost1 (myint* ant, myint* nxt)
{
idx i,k;
for (i=0; i<nn; i++) {
k = min3 (ant, i);
nxt += ant [k];
}
// print (nxt);
}
idx getMinCost ()
{
idx j;
for (j=1;j<mm;j++) {
getMinCost1 (table [j-1], table [j]);
}
return min_element (table [mm-1], table [mm-1]+nn-1)-table [mm-1];
}
void getPath (idx way)
{
short j;
cout << way+1 << " ";
for (j=mm-2; j>=0; j--) {
way = min3 (table [j], way);
cout << way+1 << " ";
}
cout << endl;
}

int main ()
{
idx k;
//printTable ();
k = getMinCost ();
getPath (k);
cout << table [mm-1][k] <<endl;
}
return 0;
}
[/cpp]

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact: It seems like I've tried all these cases relating to this problem, as well as testing tons and tons of border cases, can someone tell me if there's a trap or some really good sample output? Thanks

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
In my opinion some trouble make matrix with 1xN and 2xN ... if I handle it specially, I got Accepted after rejudgement ....

Regards
Dominik

junjieliang
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore
I was having problems with outputting the lexicographically smallest route, but I got AC after fixing that. I think that's the major problem everyone else is facing as well... I didn't handle special cases though

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:
I rewrote it from scratch and got it AC.. I also didn't check for the 1XN or 2XN.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:
I made first time small mistake with 2xN matrix ... This was a reason, why I write my last message ) if I add one condition to two if's everything was OK. So I don't handle it special too ... I see that I wrong write my thoughts )

Regards
Dominik

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

### 116 - Lexicography order

according to lexicography order, which is come first between :
1, 2, 1, 10
1, 2, 1, 2

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Second one (yeah, in this problem "lexicography" means "select lowest number").

FlyDeath
Learning poster
Posts: 73
Joined: Wed Jan 02, 2002 2:00 am
Location: Taiwan
I think everyone get WA can try this:

Code: Select all

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

output:
1 2 2 1 6 6 6
7
``````
Althought I still get WA(I'm trying to find the mistake ),but I think this is a test case that many program will make mistake.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut
i use DP, and after rejudgement i get WA. I get the same result as you post and i 've tried matrix 1xn, 2xn and nx1. and my code works. i didnt know what's wrong with my code .
firstly, i thought that the problem is in lexicography order which i thought 1, 2, 1, 10 come first than 1, 2, 1, 2. but not so.
Then i thought that perhaps data type which i use. although the path weight will not exceed integer value 30 bit, but perhaps on the way to the result it will exceed it, then i use bigger data type, but the result was the same, WA.
til now, i have no idea what's the mistake with my code .

Rodrigo
New poster
Posts: 14
Joined: Sun Jul 07, 2002 12:03 am
Location: Brazil
Contact:
Same with me. I've covered all these points too, but I still get WA :/.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
hi all,
been struggeling with this one for quite some time too, but finaly solved it by considering possible quirks in the input. my first code got accepted before rejudge and looked something like:

[pascal]while not eof do begin
for row:=1 to rows do for column:=1 to columns do read(m[row,column]);
{rest of code, calculating smallest weight and writing answer}
end;[/pascal]

after rejudge it suddenly got WA. now i changed it to:

[pascal]while not eof do begin
for row:=1 to rows do for column:=1 to columns do read(m[row,column]);
{rest of code, calculating smallest weight and writing answer}
end;[/pascal]

and got AC again!

has to do with extra spaces at the end of an input line, i guess.

happy hunting.

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact: