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

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

This is something new - WA#16
Послано Aleksander 14 авг 2009 23:07
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.
2 Admins
Послано Aleksander 15 авг 2009 12:06
When I change:
>fir,sec,op,h:array[1..1000]of integer;
>g,put:array[1..1000,1..1000]of integer;
into:
fir,sec,op,h:array[1..1050]of integer;
g,put:array[1..1050,1..1050]of integer;

and

>const inf=2005;
into:
const inf=100000;

I get AC
Maybe you'll check Test#16
Re: 2 Admins
Послано Timur Sitdikov (MSU TB) 11 мар 2011 22:24
I also had problem with test 16. I had a bug: my program couldn't work with number of rout 2000.