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.