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 1029. Ministry

So strange!!! I think my work is correct...But I stil got a WA at test#5.
Posted by Ginforward 16 Apr 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.