Virtual Object
::
Programs
:: Дейкстра |
||||
Наша кнопка |
||||
Поиск кратчайшего пути в ориентированном графе методом Дейкстры {$APPTYPE CONSOLE}
const unreal=987654;
var n,i,j: integer;
x,y,z: integer;
s,f: integer;
a: array [1..1000,1..1000] of integer;
d,mark: array [1..1000] of integer;
lmark: integer;
{----------------------------------------------}
function min(n:integer):integer;
var i,m:integer;
begin
m:=maxint;
min:=0;
for i:=1 to n do
if ((mark[i]=0)and(m>d[i])) then
begin
m:=d[i];
min:=i;
end;
end;
{----------------------------------------------}
procedure dist;
var u,i:integer;
begin
for i:=1 to n do
d[i]:=a[s,i];
d[s]:=0;
mark[s]:=1;
lmark:=n-1;
while lmark>0 do
begin
u:=min(n);
mark[u]:=1;
dec(lmark);
for i:=1 to n do
if (mark[i]=0) then
if (d[i]>(d[u]+a[u,i])) then d[i]:=d[u]+a[u,i];
end;
end;
{----------------------------------------------}
begin
assign(input,′input.txt′); reset(input);
assign(output,′output.txt′); rewrite(output);
readln(n,s,f);
for i:=1 to n do
for j:=1 to n do
a[i,j]:=unreal; {Левое число}
while not(seekeof(input)) do
begin
readln(x,y,z);
a[x,y]:=z;
end;
dist;
if d[f]=unreal then write(′Нереально′) else writeln(d[f]);
end.
|
||||
Object © 2004 - 2005. All rights reserved. |
||||