ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1072. Routing

Help! Where is that mistake?!!! (Code attached)
Posted by Alex[LSD] 30 Jun 2002 23:16
{
Its quite simple. We read the info about the computers. Then we use a
lousy N^3 algorythm to find the shortest way between the 2 computers.
This all should work but it doesnt...}

Program acm_1072; {Routing}

Type comp = Record
              Inter:array [1..5,1..4] of byte;
              Mask :array [1..5,1..4] of byte;
            End;

Var N           :integer;
    A           :array [1..100] of comp;
    C           :array [1..100] of integer;
    i,j,k,l     :integer;
    from        :array [1..100] of integer;
    con         :array [1..100,1..100] of boolean;
    First,last  :integer;

Function Numb(x:char):boolean;
Begin
  Numb:=(x>='0')and(x<='9');
End;

Function Compatible(n1,c1,n2,c2:integer):boolean;
Var i,k  :integer;
    ok1,ok2,ok3,ok4:boolean;
Begin
  ok1:=(A[n1].inter[c1,1] AND A[n1].mask[c1,1])=(A[n2].inter[c2,1]
AND A[n2].mask[c2,1]);
  ok2:=(A[n1].inter[c1,2] AND A[n1].mask[c1,2])=(A[n2].inter[c2,2]
AND A[n2].mask[c2,2]);
  ok3:=(A[n1].inter[c1,3] AND A[n1].mask[c1,3])=(A[n2].inter[c2,3]
AND A[n2].mask[c2,3]);
  ok4:=(A[n1].inter[c1,4] AND A[n1].mask[c1,4])=(A[n2].inter[c2,4]
AND A[n2].mask[c2,4]);
  Compatible:=ok1 AND ok2 AND ok3 AND ok4;
End;

Procedure ReadComp(x:integer);
Var i,j,k,l  :integer;
    num      :integer;
    S,S1     :string;
Begin
  ReadLN(K); C[x]:=K;
  For i:=1 to K do
  Begin
    ReadLn(S); S:=S+' ';
    For j:=1 to 4 do
    Begin
      {Chitaem j-i bait}
      While ( not numb(S[1]) ) do delete(S,1,1);
      S1:='';
      While Numb(S[1]) do Begin S1:=S1+S[1]; Delete(s,1,1); End;
      val(S1,A[x].inter[i,j],l);
    End;

    For j:=1 to 4 do
    Begin
      {Chitaem j-i bait}
      While ( not numb(S[1]) ) do delete(S,1,1);
      S1:='';
      While Numb(S[1]) do Begin S1:=S1+S[1]; Delete(s,1,1); End;
      val(S1,A[x].mask[i,j],l);
    End;
  End;
End;


Begin
  ReadLn(N);
  For i:=1 to N do
  ReadComp(i);

  Fillchar(con,sizeof(Con),0);

  For i:=1 to N do
    For j:=i to N do
      For k:=1 to C[i] do
        For l:=1 to C[j] do
        If Compatible(i,k,j,l) then Begin con[i,j]:=true; Con
[j,i]:=true; End;

  For i:=1 to N do C[i]:=200;
  Read(First,Last);
  C[Last]:=1;

  i:=1;
  While i<>0 do
  Begin
    i:=0;
    For j:=1 to N do
    For k:=1 to N do
    If (Con[j,k])and(C[k]>C[j]+1) then
      Begin
        From[k]:=j; i:=1; C[k]:=C[j]+1;
      End;
  End;
  If C[First]=200 then Begin Writeln('No'); Halt(0); End;
  Writeln('Yes'); k:=First;
  For i:=1 to C[First] do
  Begin
    If i<>c[first] then Write(k,' ') Else Write(k); K:=From[k];
  End;
End.