{min.sulyu feszitofa}
{Mikrologia-28, 60. oldal}
uses lista0;
{Procedure MinimalisFeszitofa;
begin
  Tav(0..Pontszam):=vegtelen;
  pont:=1; tav(pont):=0; honnan(pont):=pont;
  For i:=1 to Pontszam do begin
    For j:=1 to SzomszedpontokSzama do begin
      spont:=Szomszedpont(pont,j);
      if tav(spont)>0 (* meg nem tartozik a feszitofahoz *)
        and ElHossz(pont,spont)<Tav(spont) (* kozelebb van *)
        then begin
               Honnan(spont):=pont;
               Tav(spont):=ElHossz(pont,spont);
             end;
    end;
    MinimalisTavolsagu(pont); (* indulas a legkozelebbirol *)
  end;
end;}
{-- a lista0 unitbol --
   elemtip=record tav:byte; volte:boolean; end;
   Telem=array[1..100,1..100] of elemtip;
  tlistaelemmut=^tlistaelem;
  tlistaelem=record
    ertek:telem; kov:tlistaelemmut; end;
  tlista=object
-- unit-reszlet vege --}

type tpont=integer; {sejtheto a feladatbol: egy sorszam /1..1000/ }
      nkr=integer; {"normal koordinatak"}
const n=1000; {ezt a feladat leirasabol tudjuk}
      pontszam=n;
      vegtelen=99; {ezt csak nem mulja felul semmi}
var l:tlista;
fnev:text;
{pl: 100-elemu lista /a melyseghez/,
adattip: tgraf=array[1..100,1..100] of elemtip;}

{TP: tomb maximalis helyfoglalasa: 65,520 byte}
var tav:array[1..1000] of integer; {a tavolsagok megjegyzesehez}
    honnan:array[1..1000] of integer; {ahonnan ide jottunk: a pont sorszama}

Procedure kr2li(ax,ay:nkr; var a,b,c:integer);
{"normalis koordinatakat" konvertal a listas kereseshez}
var szum:longint;
begin {pl: 123.456 -> 12.34.56}
  szum:=(ax*1000)+ay;
  c:=(szum mod 100); szum:=szum div 100;  {az adott sorban melyik helyen}
  b:=(szum mod 100); szum:=szum div 100;  {melyik sorban}
  a:=(szum mod 100);                      {melyik listaban}
end;

Procedure li2kr(a,b,c:integer; var ax,ay:nkr);
{listas koordinatakat konvertal "normal koordinatakka"}
var szum:longint;
begin {pl: 12.34.56 -> 123.456}
  szum:=a*100; szum:=szum+b;
  szum:=szum*100; szum:=szum+c;
  ax:=szum div 1000; ay:=szum mod 1000;
end;

Procedure beolvasfile(var f:text; var e:elemtip; var x,y:integer);
{egy sort a befile-bol}
var tavsv:byte; c:char;
begin
{a file felepitese:
3_jegyu_szam, szunet, 3_jegyu_szam, szunet, 2_jegyu_szam}
{ elotte az asm-beadandom balra igazitja :-) }
  if not(eof(f)) then begin
    read(f,x); read(f,c);
    read(f,y); read(f,c);
    read(f,tavsv); readln(f); (* sorvege jelet ne dolgozza fel *)
    e.tav:=tavsv; e.volte:=false;
  end; {if}
end;

Procedure listakeszit(var l:tlista);
var x,y:byte; semmielem:elemtip; (* valamivel ki kell "tomni" *)
i:integer;
begin
  semmielem.tav:=99; semmielem.volte:=false; l.ures;
  For i:=1 to 100 do l.beszurmoge(1,1,semmielem);
end;

Procedure listafeltolt(var f:text; var l:tlista); {file 2 lista}
var e:elemtip; x,y:integer; {honnan hova} i:integer;
a,b,c:integer;
begin
  listakeszit(l);
  while not eof(f) do begin
    beolvasfile(f,e,x,y);
    kr2li(x,y,a,b,c); (* a listaban a megfelelo hely megkeresese *)
    l.elejere;
    if a>=0 then begin
      for i:=1 to (a-1) do l.kovetkezore; (* listamutato beallitasa *)
    end; (* Ha a nulladik "sikban" vagyunk, akkor nem "ugraljon" *)
    l.elemmodosit(b,c,e); (* ertekadas *)
  end; {while, eof}
end;

Procedure MinimalisTavolsagu(var pont:tpont);
{pont := azon pont, amelynel a tav[pont] a legkisebb
 - azaz egy minimumkivalasztas a tav() tomb elemeire}
var i:integer;
begin
  pont:=0;
  For i:=1 to Pontszam do begin
    if ((Tav[i]>0) and (Tav[i]<Tav[pont])) then pont:=i;
  end;
  Tav[pont]:=0;
end;

Procedure listaertek(l:tlista; a,b,c:integer; var p:elemtip);
{(a,b,c) = (listahely, sor, hely_a_sorban)}
var i:integer;
begin
  l.elejere;
  for i:=1 to a do begin
    l.kovetkezore; {melyik listaban keresunk}
  end;
    {elemtip=record tav:byte; volte:boolean; end;
   Telem=array[1..100,1..100] of elemtip;

  tlistaelemmut=^tlistaelem;
  tlistaelem=record
    ertek:telem; kov:tlistaelemmut; end;
  tlista=object
}
    p:=l.akt^.ertek[b,c]; {p:= az aktualis lista megfelelo eleme}
end;

Function Elhossz(p1,p2:nkr):byte;
var a,b,c:integer; {a listaban valo kereseshez}
    e:elemtip; {az eredmenyhez}
begin
  kr2li(p1,p2,a,b,c); {megkeressuk}
  listaertek(l,a,b,c,e); {kiolvassuk}
  elhossz:=e.tav; {atadjuk az erteket}
end;

Function SzomszedPontokSzama(pont:tpont):integer;
var a,b,c:integer; db:integer; i:integer; e:elemtip; {elemtip:rekord(x.y)}
begin
  kr2li(0,pont,a,b,c);
  db:=0; i:=1;
  while i<=pontszam do begin (* mindem pontra: o lehet-e szomszed? *)
    listaertek(l,a,b,c,e);  (* ertek kiolvasasa a listabol *)
    if e.tav<>vegtelen then inc(db); (* ha elerheto, akkor szomszed *)
    b:=b+10; (* a listas konverzio utan a listaban ennyienkent lehetnek *)
  end;
  SzomszedpontokSzama:=db;
end;

Procedure Szomszedpont(pont:tpont;hanyadik:integer; var ujpont:tpont);
var a,b,c:integer; {"kodolt" koordinatakhoz}
    x,y: integer; {a "normal" koordinatakhoz}
    segedv:integer; e:elemtip;
begin
  {- nkr-ben:
   while (a[x,y].tav<>vegtelen) do begin
     if y<>1000 then inc(y) else y:=-1;
   end;
   ujpont:=y; -}
   {- listaban: kicsit erdekes, hogy nem kell avval torodni,
   hanyadik szomszedja kell, uis nyilvan a kovetkezo lesz a kovetkezo...
    x: a_"pont"bol_kinyeri_az_"x"et}
    {inc(y); (* megnezi, a "szomszed" jo-e *)}
    x:=pont; y:=1; (* ezen a helyen vagyunk alapbol *)
    kr2li(x,y,a,b,c); (* az elso szomszed keresese *)
    {inc(y); (* megnezi, a "szomszed" jo-e *)}
    listaertek(l,a,b,c,e);
    while (e.tav=vegtelen) do begin (* amig nem talal szomszedot *)
      if y=1000 then y:=-1 (* egyaltalan nem lehet mar tobb szomszedja *)
        else begin
          inc(y); (* megy felfele *)
          kr2li(x,y,a,b,c); (* atkonvertal... *)
          listaertek(l,a,b,c,e); (* ...es kiolvassa az erteket *)
        end;
    end;
    ujpont:=y;
  {pont megkeresese}
  {a kovetkezo olyan ertek keresese, ahol a sajat
  nkr-jeben az "x" azonos, es a kovetkezo "y" nem nulla es nem vegtelen}
  {ujpont:= az nkr-tablaban az "y" - azaz "a masik pont",
  kulonben vmi nil-ertek /most (-1)/ }
end;

Procedure MinimalisFeszitofa(var l:tlista);
var i,j:integer; spont,pont:tpont;
  szpontokszama:integer; (* mivel a fv-t hivjak SzomszedPontokSzamanak *)
  Procedure TavNullaz; (* Tav(0..Pontszam):=vegtelen; *)
  var i:integer; begin For i:=1 to Pontszam do Tav[i]:=vegtelen; end;
begin
  tavnullaz;
  (* pont:=1; tav[pont]:=0; honnan[pont]:=pont; *)
  pont:=1;
  {listaertek(l,1,1,1,pont); (* pont:=elso_lista[1,1] *)}
  For i:=1 to Pontszam do begin (* nkr-ben ertelmezve a koordinatakat *)
    szpontokszama:=SzomszedpontokSzama(pont);
    For j:=1 to SzpontokSzama do begin (* szelessegi bejaras *)
      Szomszedpont(pont,j,spont);
      if ( (tav[spont]>0) (* meg nem tartozik a feszitofahoz *)
        and (ElHossz(pont,spont)<Tav[spont]) )(* kozelebb van *)
        then begin
               Honnan[spont]:=pont; (* ut megjegyzese *)
               Tav[spont]:=ElHossz(pont,spont); (* tavolsag megjegyzese *)
             end;
    end;
    MinimalisTavolsagu(pont); (* indulas a legkozelebbirol *)
  end;
end;

BEGIN
assign(fnev,'gm1000.124'); reset(fnev);
listafeltolt(fnev,l);
close(fnev);
MinimalisFeszitofa(l);
END.