{************************************************}
{                                                }
{ programma per calcolo minimo albero ricoprente }
{************************************************}

{ "Generic" Windows application written in Turbo Pascal }

program MinAlbero;

uses WinTypes, WinProcs,Wincrt;

const maxdim=50;
      maxlung=32760;
type matrice=array[1..maxdim,1..3]of integer; (* inserimento degli archi in una matrice dove
                                       le righe rappresentano il numero di archi e
                                       le colonne rispettivamente la 1- nodo di partenza
                                                                     2- nodo di arrivo
                                                                     3- lunghezza arco *)


var n,k,o:integer;                  (*  n:nodi,  k;archi,  o:nodo origine  *)
    A,T: matrice;
    flag_fine:boolean;

(* ========================   Procedura inserimento dati grafo ============================   *)
Procedure InserimentoArchi(k:integer; var A:matrice);
  var i,j:integer;     (* i scorre le righe, j =1 per nodo origine
                                               =2  "  nodo termine
                                               =3  "  valore dell'arco *)
  begin
       writeln('gli archi da inserire sono  ',k);
       writeln('inserisci archi del grafo separando nodo_inizio,nodo_fine,dist.   con spazio');
       for i:=1 to k do
         begin
           for j:=1 to 3 do
            begin
             read(A[i,j]);
            end;
            writeln;
         end;

  end;
(* ========================================================================================   *)

(* ========================   Procedura inizializzazione tabella risultati ================   *)
Procedure InizializzazioneTabella(n,o: integer; var T:matrice);
  var i,j:integer;    (* i scorre le righe della tabella risultati
                           =1 per nodo termine del percorso
                           =2  "  distanza dal nodo iniziale
                           =3  "  nodo che precede quello selezionato, nel percorso *)
  begin
       for i:=1 to n do
          begin
            T[i,1]:=i;
            T[i,2]:=maxlung;
            T[i,3]:=0;
          end;
       T[o,2]:=0;
  end;
(* ========================================================================================   *)

(* ========================   Procedura stampa tabella risultati ==========================   *)
Procedure StampaTabella(o:integer;T:matrice);
  var i,j:integer;    (* i scorre le righe,
                           =1 per nodo termine del percorso
                           =2  "  distanza dal nodo iniziale
                           =3  "  nodo che precede quello selezionato, nel percorso *)
  begin
       writeln('-----------------------------------------------------------');
       writeln('            distanza dal nodo  ', o);
       writeln('fino a ---  distanza  -- nodo che lo precede nell''albero --');

       for i:=1 to n do
         begin
          for j:=1 to 3 do
             write(T[i,j], '     ');
          writeln;
         end;
  end;
(* ========================================================================================   *)

(* ========================   Procedura calcolo percorsi ==================================   *)
Procedure Percorsi;
  var i,nodo1,nodo2,valore:integer;    (* i scorre le righe,
                                       nodo1 assume il valore A[i,1]
                                       nodo2    "    "   "    A[i,2]
                                       valore   "    "   "    A[i,3] *)
      temp:integer;
  begin
       flag_fine:=false;
       for i:=1 to k do
          begin
            nodo1:= A[i,1];
            nodo2:= A[i,2];
            valore:=A[i,3];
            if  T[nodo1,2] <> maxlung  then
                begin
                 temp:=T[nodo1,2]+A[i,3];
                 if temp< T[nodo2,2] then
                                      begin
                                        T[nodo2,2]:=temp;
                                        T[nodo2,3]:=A[i,1];
                                        flag_fine:=true;
                                      end;
                end;

            if  T[nodo2,2] <> maxlung  then
                begin
                 temp:=T[nodo2,2]+A[i,3];
                 if temp< T[nodo1,2] then
                                      begin
                                        T[nodo1,2]:=temp;
                                        T[nodo1,3]:=A[i,2];
                                        flag_fine:=true;
                                      end;
                end;

          end;
  end;
(* ========================================================================================   *)

(* ========================   Programma Principale  ========================================   *)

begin
writeln('programma per il calcolo del minimo albero ricoprente dato in input un grafo ');
writeln('con n nodi e k archi e selezionando il nodo origine tra quelli presenti');
repeat
  writeln('inserisci numero intero che rappresenta il numero di nodi');
  readln(n)
until n <> 0;
repeat
  writeln('inserisci numero intero che rappresenta il numero di archi');
  readln(k)
until k <> 0;
repeat
  writeln('inserisci numero intero che rappresenta il nodo origne compreso tra 1 e ',n);
  readln(o)
until o <> 0;
InserimentoArchi(k,A);
InizializzazioneTabella(n,o,T);
flag_fine:=true;
while flag_fine=true do  Percorsi;
StampaTabella(o,T);
end.