ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1072. Маршрутизация

Help! Where is that mistake?!!! (Code attached)
Послано Alex[LSD] 30 июн 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.