116 - Unidirectional TSP

[cyfra]

Hi!

You have a small mistake....

You have a table [1..100,1..10,1..2] while you should have [1..10,1..100,1..2]

If you change it you will have Accepted...

Good Luck

[rascle]

after rejudge..

I always got WA...

Can anyone give me some sample input and sample output..

thx... [/c]

[youngwook]

what's wrong??

help me..

[c]@BEGIN_OF_SOURCE_CODE
/* @JUDGE_ID: ******** 116 C "Dynamic Programming" */

main()
{
int row, col, i, j, path, a, b, c;
long weight[10][100];
long small;

while (scanf("%ld %ld", &row, &col) == 2)
{
for (i=0; i<row; i++)
for (j=0; j<col; j++)
scanf("%ld", &weight[j]);

for (j=col-2; j>=0; j--)
for (i=0; i<row; i++)
{
a = weight[(i-1+row)%row][j+1];
b = weight[j+1];
c = weight[(i+1)%row][j+1];
if (a < b) {
if (c < a)
weight[j] += c;
else
weight[j] += a; }
else {
if (b > c)
weight[j] += c;
else
weight[j] += b; }
}

path=0;
small=weight[path][0];
for (i=1; i<row; i++)
if (weight[0] < small) {
path=i; small=weight[path][0];
}
printf("%d", path+1);

for (j=1; j<col; j++)
{
i=path;
a = weight[(i-1+row)%row][j];
b = weight[j];
c = weight[(i+1)%row][j];
if (a < b) {
if (c < a)
path = (i+1)%row;
else if (c > a)
path = (i-1+row)%row;
else
path = ((i+1)%row < (i-1+row)%row) ? (i+1)%row : (i-1+row)%row; }
else if (a > b) {
if (b > c)
path = (i+1)%row;
else if (b < c)
path = i;
else
path = ((i+1)%row < i) ? (i+1)%row : i; }
else {
if (c < b)
path = (i+1)%row;
else
path = ((i-1+row)%row < i) ? (i-1+row)%row : i; }
printf(" %d", path+1);
}

printf("\n%ld\n", small);

}
}

@END_OF_SOURCE_CODE [/c]

[karl]

first of all:

don't send your acm-ID (21201...) here!


second:

what was judge's reply: WA or Compile Error?
I got compile error, because <stdio.h> wasn't included.


best wishes!

karl

[vivid]

What does Lexicographically mean?
For example what is first in lexicographical order
1 1 1 3 4
or
1 10 9 8 7
??
Maybe it is your problem?

[youngwook]

first of all:

don't send your acm-ID (21201...) here!

ok.. thanx

what was judge's reply: WA or Compile Error?
I got compile error, because <stdio.h> wasn't included.

i got WA..

Your program has not solved the problem. It ran during 0.670 seconds.

.......!!

[youngwook]

What does Lexicographically mean?
For example what is first in lexicographical order
1 1 1 3 4
or
1 10 9 8 7
??
Maybe it is your problem?

i think '1 1 1 3 4' is right ans.
isn't it first?

[wenzhi cai]

Can anyone tell me what does "Lexicographically" mean?
Is sequence "1 2 3 4" less than "4 3 2 1"?

[Chung Ha, Yun]

Sequence "1,2,3,4" is less than "4,3,2,1" Lexicographically.

Answer sequence is minimum Lexicographically sequence...^^;;;

[wenzhi cai]

Then I really can't understand why I get WA.Is there anything tricky in this problem?

[przygoda]

Please help me
What is wrong with my code ???

Code: Select all

[/pascal]
  program od_nowaaaa;

   var
   t:array[1..10,1..110] of longint;
    k:array[1..10,1..110,1..2] of longint;
     i1,min,pom,n,m,i,j,a:longint;
      wynik,posrednik:array[1..110] of longint;

  procedure prepare;
   begin

   for i:=1 to n do
    for j:=1 to m do begin
     k[i,j,1]:=2147483647;
      k[i,j,2]:=15;
       end;
    end;

 begin

    while not eof do begin
     readln(n,m);
      prepare;
       i:=1;j:=0;
     while (i<>n) or (j<>m) do begin
      while not eoln do begin
       read(a);
        inc(j);
       if j > m then begin
         inc(i);
          j:=1;
           end;
       t[i,j]:=a;
        end;
         readln;
          end;

     for i:=1 to n do
      k[i,1,1]:=t[i,1];

    for j:=1 to m-1 do
     for i:=1 to n do begin

      pom:=i-1;
      if pom=0 then pom:=n;

     if k[pom,j+1,1] > k[i,j,1]+t[pom,j+1] then begin
         k[pom,j+1,1]:=k[i,j,1]+t[pom,j+1] ;
          k[pom,j+1,2]:=i;
           end
     else
       if (k[pom,j+1,1] = k[i,j,1]+t[pom,j+1]) and (k[pom,j+1,2] > i) then
           k[pom,j+1,2]:=i;

     pom:=i;

       if k[pom,j+1,1] > k[i,j,1]+t[pom,j+1] then begin
         k[pom,j+1,1]:=k[i,j,1]+t[pom,j+1] ;
          k[pom,j+1,2]:=i;
           end
     else
       if (k[pom,j+1,1] = k[i,j,1]+t[pom,j+1]) and (k[pom,j+1,2] > i) then
           k[pom,j+1,2]:=i;

    pom:=i+1;
     if pom > n then pom:=1;

         if k[pom,j+1,1] > k[i,j,1]+t[pom,j+1] then begin
         k[pom,j+1,1]:=k[i,j,1]+t[pom,j+1] ;
          k[pom,j+1,2]:=i;
           end
     else
       if (k[pom,j+1,1] = k[i,j,1]+t[pom,j+1]) and (k[pom,j+1,2] > i) then
           k[pom,j+1,2]:=i;

     end;

  min:=2147483647 ;
                   for i:=1 to 105 do   wynik[i]:=11;

   for i:=1 to n do
     if k[i,m,1] < min then min:=k[i,m,1] ;

     for i:=1 to n do
      if k[i,m,1] = min then   begin

    i1:=i;
     posrednik[m+1]:=i;

       for pom:=m  downto  1  do begin
      posrednik[pom]:=k[i1,pom,2];
       i1:=k[i1,pom,2];
        end;

    i1:=m+2;
   while wynik[i1]= posrednik[i1] do dec(i1);
    if wynik[i1] > posrednik[i1] then
     for i1:=1 to m+2 do
      wynik[i1]:=posrednik[i1];

       end;

    for i:=2 to m do
     write(wynik[i],' ');
      write(wynik[m+1]);
       writeln;
        writeln(min);

   for i:=1 to 105 do posrednik[i]:=11;




 end;
end.

[zerocool]

Input :
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

Output
2 1 6 5 4 3 3 3
8

Try Try ..^_^..I wish this can help you..

[Dominik Michniewski]

I got the same result as you post, but I got WA after rejudgement too.... Is any trap (after rejudgement) in this problem ??

Dominik Michniewski

[arc16]

Please help...
I'm getting TLE by using DFS.
Is there any faster method?

[ithamar]

I'm getting TLE by using DFS.
Is there any faster method?

I think that this problem can be solved using DP. And i think that DP is a LOT more efficient that DFS.

Hope this can help.