понедельник, 10 октября 2011 г.

Дейкстра нашем исполнении :) (ОЛИМПИАДНАЯ ПОДГОТОВКА)

Алгоритм Дейкстры от Вадима (10Д). Ждем Андрея, Антона, Женю и Вову!
Как я и говорила, вы уже смогли увидеть матрицу, осталось совсем чуть-чуть!


program Project1;
{$APPTYPE CONSOLE}

uses
  SysUtils;
type mas=array[1..100,1..100] of integer;
  var R,m2,next:array[1..100] of integer; a:mas; N,S,F,i,j,nr:integer; f1,f2:text;
  procedure sosedi(x:integer);
  var i2:integer;
  begin
    for i2:=1 to N do
  if (a[x,i2]>-1) and (x<>i2) then
  if R[i2]=3 then
  begin
  R[i2]:=2;
  m2[i2]:=m2[x]+a[x,i2];
  inc(nr); next[nr]:=i2;
  end
  else if R[i2]=2 then
  if m2[i2]>m2[x]+a[x,i2] then begin m2[i2]:=m2[x]+a[x,i2];
  inc(nr); next[nr]:=i2;
  end;
  end;
begin
  try
    { TODO -oUser -cConsole Main : Insert code here }
  except
    on E: Exception do
      Writeln(E.ClassName, ': ', E.Message);
  end;
  assign(f1,'Input.txt');
  reset(f1);
  read(f1,N,S,F);
  readln(f1);
  for i:=1 to N do begin
  for j:=1 to N do
  read(f1,a[i,j]);
  readln(f1);
  end;
  close(f1);
  for i:=1 to N do
   m2[i]:=-1;
  m2[S]:=0;
  for i:=1 to N do
   R[i]:=3;
  R[S]:=1;
  next[1]:=S; nr:=1;
  while nr>0 do begin
  sosedi(next[1]);
  next[1]:=next[nr];
  nr:=nr-1;
  end;
  assign(f2,'Output.txt');
  rewrite(f2);
  writeln(f2,m2[F]);
  close(f2);
end.