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

Обсуждение задачи 1029. Министерство

So strange!!! I think my work is correct...But I stil got a WA at test#5.
Послано Ginforward 16 апр 2008 20:53
I checked the standard output. It is the same as mine...

 Why?????



program ural1029;
var
 tot,dep,now,m,n,las,i,j:longint;
 f:array[1..100,1..500]of qword;
 dp:array[1..100,1..500]of qword;
 last:array[1..500]of qword;
 route:array[1..100,1..500,1..2]of integer;
 flag:boolean;
 min:qword;
 ans:array[1..50000]of integer;


begin
 readln(m,n);
 if (m=1)and(n=1) then begin writeln(1); halt; end;
 for i:=1 to m do begin
  for j:=1 to n do
   read(f[i,j]);
  readln;
 end;
 for i:=1 to n do dp[1,i]:=f[1,i];
 for i:=2 to m do
  for j:=1 to n do dp[i,j]:=1 shl 30;
 for i:=1 to n do last[i]:=1 shl 30;
 if m>=2 then begin
 for i:=2 to m do
   repeat
    flag:=true;
    for j:=1 to n do begin
     if dp[i-1,j]+f[i,j]<dp[i,j] then begin
      dp[i,j]:=dp[i-1,j]+f[i,j];
      route[i,j,2]:=j;
      route[i,j,1]:=i-1;
     end;
     if j>1 then if dp[i,j-1]+f[i,j]<dp[i,j] then begin
      dp[i,j]:=dp[i,j-1]+f[i,j];
      route[i,j,2]:=j-1;
      route[i,j,1]:=i;
     end;
     if j<n then if dp[i,j+1]+f[i,j]<dp[i,j] then begin
      dp[i,j]:=dp[i,j+1]+f[i,j];
      route[i,j,2]:=j+1;
      route[i,j,1]:=i;
     end;
    end;
    for j:=1 to n do if last[j]<>dp[i,j] then
            begin flag:=false; break;
            end;
    if not flag then for j:=1 to n do
            last[j]:=dp[i,j];
   until flag;
   min:=1 shl 30;
  for i:=1 to n do if dp[m,i]<min then begin
    min:=dp[m,i];
    las:=i;
    end;
   now:=las; dep:=m;  tot:=1;
   ans[tot]:=now;
   while route[dep,now,1]<>0 do begin
    now:=route[dep,now,2];
    dep:=route[dep,now,1];
    inc(tot);
    ans[tot]:=now;
   end;
   writeln(now);
   for i:=tot downto 1 do writeln(ans[i]);
  end
  else begin
    min:=1 shl 30;
    for i:=1 to n do if f[1,i]<min then begin min:=f[1,i]; las:=i; end;
        writeln(las);
       end;
end.