Can you give me any hint or any tests?

Thanks in advance.

Why always getting mle on #2

In this problem,many people use the BFS(breadth first search).However,you can't search it from the two numbers which are in the last line,you should search it from the plate you need.Because of this,I was wrong before at test#6.

If your can't understand it,you can test the sample input,the right answer is-
2
1
2
but not 2
4
2

And pay attention at the number of routes-1 to 2000.

Believe me!!!

Sorry to my English...I'm a Chinese...

Good luck to you.:)

I used Djkstra search. Why didn't this work?
By the way, is 1<=K<=1000 or K may become zero or negative?

My AC probram gets on samle test output
2
2
1
However this is an output of reversed sequence. It is even imposible to change 1/8 to 5/4.
Good output:
2
1
2

What is more, in the problem statement is not written that any one shortest way of changing can be printed. Even for sampe test there are 2 way of solving it.

Sorry for mine English.

Maybe those tests are not correct in 100% but answers are are good ;)


11
8 4
3 5
10 3
5 1
2 9
1 4
8 4
9 6
9 10
9 2
6 9
5 6 9
###################################
3
9
3
2


9
8 5
8 2
7 10
9 10
1 4
1 9
9 7
3 8
4 8
8 1 5
##############################
2
5
9




9
3 6
4 6
4 9
5 1
2 4
10 8
5 7
8 4
6 2
1 9 5
####################################
1
4

I've checked my program many times, but I didn't see any mistake in it
Maybe you can see
Thanks

const inf=2005;

var i,j,x,k,need,sh,zn,num:integer;
fir,sec,op,h:array[1..1000]of integer;
g,put:array[1..1000,1..1000]of integer;
f:boolean;

      procedure deikstra;
      begin
      while (sh<k+1)do begin
      zn:=inf;
      num:=-1;
      for i:=1 to k+1 do begin
        if (op[i]<zn)and(h[i]=0)then begin
        zn:=op[i];
        num:=i;
        end;
      end;
      if (num=-1)then exit;
      h[num]:=1;
      inc(sh);
      for i:=1 to k+1 do begin
        if (g[num,i]=1)and(op[i]>op[num]+1)and(h[i]=0)then begin
        op[i]:=op[num]+1;
        for x:=1 to op[num] do put[i,x]:=put[num,x];
        put[i,op[i]]:=num;
          if (fir[i]=need)or(sec[i]=need)then begin
          writeln(op[i]);
          for x:=2 to op[i] do writeln(put[i,x]);
          write(i);
          f:=true;
          exit;
          end;
        end;
      end;
      end;
      end;

begin
read(k);
for i:=1 to k do read(fir[i],sec[i]);
read(need,fir[k+1],sec[k+1]);
for i:=1 to k+1 do begin
  for j:=1 to k+1 do begin
    if ((fir[i]=fir[j])or(fir[i]=sec[j]))and(i<>j)then begin
    g[j,i]:=1;
    end;
  end;
end;
for i:=1 to k+1 do op[i]:=inf;
op[k+1]:=0;
sh:=1;
f:=false;
deikstra;
if (f=false)then write('IMPOSSIBLE');
end.

may be you forgot <= 1000 but not < 1000??

Who can give me some test to debug WA#2?
I can't found, where is mistake?

I use BFS. Main idea is rather simple.
I have rewrited my program 2 times, but still WA#8

Edited by author 02.07.2009 20:30

any one can give me some tips? what's the test1 is ??

1
1 3
3 2 1
ANSWER:
1
1

but

1
3 1
3 2 1
ANSWER:
IMPOSSIBLE

what data for this test???

It seems we must output the shortest way of changing,but in the problem says:
If there are several solutions, you can output any one.
isn't it wrong?

sorry for my english.

I use BFS in the program
#include<iostream.h>
long x[2000],y[2000];
int queue[2000];
int parent[2000];
int path[2000];
int in[2000];
void main()
{

 int n;
 int i,j,tot,current,step;
 int temp;
 long need;
 cin>>n;
 for(i=1;i<=n;i++){
   in[i]=0;
   cin>>x[i]>>y[i];
 }
 cin>>need>>x[0]>>y[0];

 queue[0]=0;
 current=0;
 tot=1;
 while(current<tot){
     if(x[queue[current]]==need||y[queue[current]]==need) break;
     for(i=1;i<=n;i++){
         if(!in[i]){
             if((x[i]==x[queue[current]])||(x[i]==y[queue
[current]])||(y[i]==x[queue[current]])||(y[i]==y[queue[current]])){
               queue[tot]=i;
               parent[i]=queue[current];
               in[i]=1;
               tot++;
             }
         }
     }
     current++;
 }

 if(x[queue[current]]==need||y[queue[current]]==need){
     step=0;
     temp=queue[current];
     while(1){
      if(temp==0) break;
      step++;
      path[step]=temp;
      temp=parent[temp];
     }
     cout<<step<<endl;
     for(j=step;j>=1;j--){
      cout<<path[j]<<endl;
     }
 }else{
  cout<<"IMPOSSIBLE"<<endl;
 }
}

Thanks to sb.
I WA first.But I AC after I knew K might >1000
!!!!!
Be careful!

In the problem do not written how much defferent routes are
availble!!!