MELE3 - MELE3

Tác giả: flashmt

Ngôn ngữ: Pascal

const maxn=2000;
var a:array[1..maxn,1..maxn] of byte;
    d:array[1..maxn] of longint;
    dau:array[1..maxn] of byte;
    n:integer;
    m:longint;

procedure rf;
var i:longint; x,y:integer;
begin
     fillchar(a,sizeof(a),0);
     readln(n,m);
     for i:=1 to m do
     begin
          readln(x,y);
          a[x,y]:=1; a[y,x]:=1;
     end;
end;

procedure pr;
var i,j,cur,temp:integer;  t,u,min:longint;
begin
     fillchar(dau,sizeof(dau),0);
     for i:=1 to n do d[i]:=maxlongint;
     j:=1; dau[1]:=1; cur:=1; d[1]:=0;
     repeat
           for i:=1 to n do
               if (dau[i]=0) and (a[cur,i]=1) then
               begin
                    if i<cur then
                    begin
                         t:=2*(cur-i);
                         if d[cur] mod t = cur-i then u:=cur-i
                         else u:=cur-i+d[cur] mod t;
                    end
                    else
                    begin
                         t:=2*(i-cur);
                         if d[cur] mod t = 0 then u:=i-cur
                         else u:=i-cur+t-d[cur] mod t;
                    end;
                    if d[cur]+u<d[i] then d[i]:=d[cur]+u;
               end;
           min:=maxlongint;
           for i:=1 to n do
               if (dau[i]=0) and (d[i]<min) then
               begin
                    min:=d[i];
                    temp:=i;
               end;
           cur:=temp; dau[cur]:=1;
     until (dau[n]=1) or (j=n);
end;

procedure wf;
begin
     write(d[n]*5);
end;

begin
     rf;
     pr;
     wf;
end.

Download