program p_einbaum;                  (* minimaler 1-Baum, Thomas Klein  1999 *)
uses graph,tsp;
var add:stadtnr;

procedure einbaum(add:stadtnr;var t:weg);
 (* berechnet min. 1-Baum, add: am Ende hinzuzufuegende Stadt *)
 var n,i,j,i2,j2:stadtnr;
     e:array [1..maxstadtquad] of record i,j:stadtnr; end;
     w:array [1..maxstadt] of entfernung;
     s:set of stadtnr;
     l,m,l2,m2:entfernung;
     k:word;
 begin
  case stadtanzahl of
   1: t:='';
   2: t:=#2#1#2;
   else begin
    (* MST fuer 1..stadtanzahl ohne add berechnen *)
    k:=0;
    for i:=1 to stadtanzahl do
     if i<>add then
      for j:=1 to stadtanzahl do
       if j<>add then begin inc(k); e[k].i:=i; e[k].j:=j; end;
    n:=stadtanzahl-1;
    w[1]:=0; s:=[1..n]; t:='';
    for i:=2 to n do w[i]:=maxentfernung;
    while s<>[] do begin
     l:=maxentfernung;
     for j:=1 to n do
      if (j in s) and (w[j]<=l) then begin i:=j; l:=w[j]; end;
     s:=s-[i];
     if e[i].i<>e[i].j then begin
      if t='' then
       t:=chr(e[i].i)
      else
       if ord(t[length(t)])<>e[i].i then t:=t+chr(0)+chr(e[i].i);
      t:=t+chr(e[i].j);
     end;
     for k:=1 to n*n do begin
      i:=e[k].i; j:=e[k].j; l:=entftab[i,j];
      if i>=add then dec(i);      (* Anpassung an geaenderte *)
      if j>=add then dec(j);      (*       Numerierung       *)
      if not(i in s) and (j in s) then
       if w[j]>l then begin w[j]:=l; e[j]:=e[k]; end;
     end;
    end;
    (* add hinzufuegen *)
    l:=maxentfernung; l2:=maxentfernung; m:=maxentfernung; m2:=maxentfernung;
    for n:=1 to stadtanzahl do
     if (n<>add) then begin
      if (entftab[n,add]<l) then begin
       l2:=l; i2:=i; l:=entftab[n,add]; i:=n;
      end else
       if entftab[n,add]<l2 then begin l2:=entftab[n,add]; i2:=n; end;
      if (entftab[add,n]<m) then begin
       m2:=m; j2:=j; m:=entftab[add,n]; j:=n;
      end else
       if entftab[add,n]<m2 then begin m2:=entftab[add,n]; j2:=n; end;
     end;
    if i=j then begin
     if l+m2<l2+m then j:=j2 else i:=i2;
    end;
    if t='' then t:=chr(i);
    if ord(t[length(t)])<>i then t:=t+chr(0)+chr(i);
    t:=t+chr(add)+chr(j);
   end;
  end;
 end;

begin
 if tspinit('Minimaler 1-Baum','Berechnen') then
  while tspmenue([0..255]) do begin
   meldung('Hinzuzufgenden Punkt w„hlen!',green,white);
   add:=stadtwahl(255);
   start; einbaum(add,aktuell); stop;
   wegkarte(aktuell,true,brown,yellow);
   laenge_aus(aktuell); zeit_aus(true);
  end;
 closegraph;
end.