116  Unidirectional TSP
Moderator: Board moderators

 New poster
 Posts: 19
 Joined: Fri Oct 04, 2002 7:50 pm
 Location: Warsaw, Poland
Need helps !!!
I don't know why my code got WA. Please help !
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;
Procedure Readfile;
var i,j :longint;
begin
read(m,n);
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:=i1 to i+1 do
begin
u:=k;
if u=0 then u:=m;
if u=m+1 then u:=1 ;
if l[u,j1]>l[i,j]+a[u,j1] then
begin
l[u,j1]:=l[i,j]+a[u,j1];
pre[u,j1]:=i;
end
else if (l[u,j1]=l[i,j]+a[u,j1]) and (pre[u,j1]>i) then
begin
pre[u,j1]:=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 n1 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
Readfile;
if (m=0) and (n=0) then break;
inc(test);
if test>1 then writeln;
Process ;
end;
{ close(output);
close(input);}
end.[/pascal][/code]
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;
Procedure Readfile;
var i,j :longint;
begin
read(m,n);
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:=i1 to i+1 do
begin
u:=k;
if u=0 then u:=m;
if u=m+1 then u:=1 ;
if l[u,j1]>l[i,j]+a[u,j1] then
begin
l[u,j1]:=l[i,j]+a[u,j1];
pre[u,j1]:=i;
end
else if (l[u,j1]=l[i,j]+a[u,j1]) and (pre[u,j1]>i) then
begin
pre[u,j1]:=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 n1 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
Readfile;
if (m=0) and (n=0) then break;
inc(test);
if test>1 then writeln;
Process ;
end;
{ close(output);
close(input);}
end.[/pascal][/code]
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;
bool readNextTable ()
{
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 [mmi1][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==(nn1))
return 0;
return i+1;
}
idx getPrev (idx i)
{
if (i==0)
return nn1;
return i1;
}
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 [j1], table [j]);
}
return min_element (table [mm1], table [mm1]+nn1)table [mm1];
}
void getPath (idx way)
{
short j;
cout << way+1 << " ";
for (j=mm2; j>=0; j) {
way = min3 (table [j], way);
cout << way+1 << " ";
}
cout << endl;
}
int main ()
{
idx k;
while (readNextTable ()) {
//printTable ();
k = getMinCost ();
getPath (k);
cout << table [mm1][k] <<endl;
}
return 0;
}
[/cpp]
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;
bool readNextTable ()
{
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 [mmi1][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==(nn1))
return 0;
return i+1;
}
idx getPrev (idx i)
{
if (i==0)
return nn1;
return i1;
}
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 [j1], table [j]);
}
return min_element (table [mm1], table [mm1]+nn1)table [mm1];
}
void getPath (idx way)
{
short j;
cout << way+1 << " ";
for (j=mm2; j>=0; j) {
way = min3 (table [j], way);
cout << way+1 << " ";
}
cout << endl;
}
int main ()
{
idx k;
while (readNextTable ()) {
//printTable ();
k = getMinCost ();
getPath (k);
cout << table [mm1][k] <<endl;
}
return 0;
}
[/cpp]

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 Experienced poster
 Posts: 169
 Joined: Wed Oct 31, 2001 2:00 am
 Location: Singapore

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:

 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
1, 2, 1, 10
1, 2, 1, 2

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
I think everyone get WA can try this:
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.
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

 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 .
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 .
 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
readln(rows,columns);
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
readln(rows,columns);
for row:=1 to rows do for column:=1 to columns do read(m[row,column]);
readln;
{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.
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
readln(rows,columns);
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
readln(rows,columns);
for row:=1 to rows do for column:=1 to columns do read(m[row,column]);
readln;
{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.