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

Обсуждение задачи 1096. Таблички с номерами маршрутов

Help me! Got WA
Послано Koala 20 авг 2003 15:08
program p1096;

const
  maxn=1000;

type
  platetype=array [1..2] of longint;

var
  a:array [1..maxn] of platetype;
  fa,q:array [1..maxn] of longint;
  visit:array [1..maxn] of boolean;
  n,i,tail,head,j,target:longint;
  u:platetype;

  procedure print(j,step:longint);
  begin
    if j=0 then
    begin
      writeln(step);
      exit;
    end;
    print(fa[j],step+1);
    writeln(j);
  end;

begin
  read(n);
  for i:=1 to n do read(a[i,1],a[i,2]);
  read(target,u[1],u[2]);

  fillchar(visit,sizeof(visit),0);
  fillchar(fa,sizeof(fa),0);
  tail:=0;
  for i:=1 to n do
    if (u[1]=a[i,1]) or (u[2]=a[i,1]) then
    begin
      visit[i]:=true;
      inc(tail); q[tail]:=i;
    end;
  head:=1;

  while head<=tail do
  begin
    i:=q[head];
    for j:=1 to n do
      if not(visit[j]) and ((a[i,1]=a[j,1]) or (a[i,2]=a[j,1])) then
      begin
        visit[j]:=true;
        fa[j]:=i;
        inc(tail); q[tail]:=j;
        if (a[j,1]=target) or (a[j,2]=target) then
        begin
          print(j,0);
          halt;
        end;
      end;
    inc(head);
  end;

  writeln('IMPOSSIBLE');
end.