*Camy si Oana au gasit *Camy si Oana au gasit o harta a Tarii o harta a Tarii Hategului, pe care au Hategului, pe care au incadrat localitatiile pe incadrat localitatiile pe care le vom vizita si prin care le vom vizita si prin care vom trece:Hateg, care vom trece:Hateg, Ciopeia, Salasu de Jos, Ciopeia, Salasu de Jos, Salasu de Sus, Salasu de Sus, MalaiestiMalaiesti, Ohaba, , Ohaba, Baiesti, Baiesti, VaideiVaidei, Galati, , Galati, FizestiFizesti,, Pui, Pui, HobitaHobita, , Rusor, Rusor, SerelSerel,, Santamarie, Santamarie, Valea Valea DaljiiDaljii, Totesti, Hatagel, , Totesti, Hatagel, Tustea, Farcadin, Tustea, Farcadin, General Berthelot, General Berthelot, CraguisCraguis, Hateg(din nou , Hateg(din nou acasa).acasa).

Ionut a desenat pe foaie harta traseului. Dan a cautat o solutie pentru a vizita o singura data toate satele, traseul sa fie parcurs cu cost minim, iar dupa ultima localitate vizitata sa ne intoarcem in orasul de plecare, Hateg.

Camy: Si in vacanta folosim grafurile de la orele de informatica?Nu-i asa ca satele reprezinta varfurile grafului iar drumurile sunt arcele?Oana:Da, dar acum trebuie sa gasim o modalitate ca sa rezolvam ceea ce ne-am propus. Avem nevoie de o modalitate de reprezentare a grafului, astfel incat sa asociem fiecarei muchii un numar real care sa corespunda distantei dintre 2 varfuri(localitati).Camy:Daca alegem ca reprezentare matricea de adiacenta, dar in care sa completam cu 1 in cazul in care exista arc si cu 0 in caz contrar, facand urmatoarea modificare: a[i,j]= distanta dintre orasele i si j.Ce ziceti,merge?Roxy:Este o solutie buna!

Procedure minim(var Dm:mat_ad);Procedure minim(var Dm:mat_ad);var i,j,k:integer;var i,j,k:integer; BeginBegin Dm:=c;Dm:=c; for k:=1 to n dofor k:=1 to n do for i:=2 to n dofor i:=2 to n do for j:=1 to n dofor j:=1 to n do if (k<>i) and(k<>j)if (k<>i) and(k<>j) then if Dm[i,k]+Dm[k,j]<Dm[i,j]then if Dm[i,k]+Dm[k,j]<Dm[i,j] then Dm[i,j]:=Dm[i,k]+Dm[k,j];then Dm[i,j]:=Dm[i,k]+Dm[k,j]; End;End;BEGINBEGINclrscr;clrscr;citire(c,n);citire(c,n);minim(Dm);minim(Dm);for i:=1 to n dofor i:=1 to n do beginbegin for j:=1 to n dofor j:=1 to n do Write(Dm[i,j],' ');Write(Dm[i,j],' '); writeln;writeln; end;end;readln;readln;end.end.

program program vacanta_Pasti_drum_scrut_si_cost_minivacanta_Pasti_drum_scrut_si_cost_minim;m;type mat_ad=array[1..50,1..50]of type mat_ad=array[1..50,1..50]of integer;integer;var c,Dm:mat_ad; {c=matricea var c,Dm:mat_ad; {c=matricea costurilor}costurilor} n,i,j:integer;n,i,j:integer;Procedure citire(var c:mat_ad;var Procedure citire(var c:mat_ad;var n:integer);n:integer);var f:text;var f:text; x,m,i,j:integer;x,m,i,j:integer; BeginBegin Assign(f,'cost.txt');Assign(f,'cost.txt'); Reset(f);Reset(f); Readln(f,n);Readln(f,n); Readln(f,m);Readln(f,m); for i:=1 to n dofor i:=1 to n do for j:=1 to n dofor j:=1 to n do if i=j then c[i,j]:=0if i=j then c[i,j]:=0 else c[i,j]:=maxint;else c[i,j]:=maxint; for i:=2 to m dofor i:=2 to m do beginbegin readln(f,i,j,x); {x=cost}readln(f,i,j,x); {x=cost} c[i,j]:=x;c[i,j]:=x; end;end; close(f);close(f); End;End;