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