Gigel şi Dorel

-şmecheri de şmecheri informaticieni-

Gigel s-a mutat într-un oraş nou! Fiind sâmbătă seara şi plictisindu-se acasă…

…el hotăraste să “îşi facă cinste” cu o bere. Pentru a se familiariza cu barurile din împrejurimi a cumpărat harta oraşului şi a bifat barurile pe hartă, fiecare bar aflându-se pe câte o stradă.

Harta fiind alcătuită din M străzi de diferite lungimi, cu sens unic si N baruri. Până la primul bar, Gigel s-a descurcat, însă de acolo lucrurile nu au mai fost aşa simple.

A luat harta şi a început să alcătuiască un traseu care porneşte din barul în care se afla, şi ajunge la toate celelalte baruri în care vrea să se cinstească.

Deşi dorinţa lui de “explorare” este mare, “condiţia lui fizică” nu este tocmai bună, astfel vrea să găsesască un traseu în care suma lungimilor străzilor parcurse să fie minimă.

Singur nu a reuşit să gaseasca drumul cel bun. Şi când credea că nu mai are şanse de reuşită a auzit o voce cunoscută:

-Două beri aici , vă rog!...era Dorel, prietenul său şi, ştiind că fusese campion pe

sate la informatică, îl roagă să îl ajute. -Dorele, tu eşti salvarea mea. Ştiu că le ai cu informatica,

aşa că scoate-mă din încurcatura asta…şi dă şi berea aia, să nu zici că te refuz!

-Bine, Gigele! Dar să ştii că dureaza mai mult de două beri.

-Ok. Dă-mi bani că fac eu cinste.

-Gigele, soluţia cea mai bună pentru problema ta ar fi algoritmul lui Dijkstra, un algoritm care calculează drumurile de cost minim de la un bar la toate celelalte. Algoritmul porneşte de la un graf orientat cu N noduri, în cazul tău baruri. De asemenea, e nevoie de un nod de start aparţinând grafului…deci baru’ ăsta.

-Dorele, pare simplu dar eu tot nu prea înteleg. Explică-mi mai bine.

-Hai ca îţi explic, da’ mai întâi hai să mai luăm o bere că poate aşa pricepi mai bine.

-Deci, fii atent la desen, ăsta este un graf orientat, iar un graf orientat este (G) o pereche ordonata de mulţimi (X,U), unde X este o mulţime finită şi nevidă de elemente , iar U o mulţime de perechi ordonate formate cu elemente distincte din mulţimea X.

Să zicem că toate astea sunt barurile şi străzile din oraş. Tu eşti in barul A şi vrei să ajungi cât mai repede la toate celelalte baruri.

Uită-te la următorul tabel:

Tabloul D are câte o intrare pentru fiecare nod al grafului, corespunzând lungimii drumului minim de la barul A până la respectivul bar.Numim drum o succesiune de noduri care au proprietatea că oricare ar fii două noduri succesive ele sunt legate printr-un arc.Astfel, drumul minim de la A la A nu te interesează (-), drumul minim de la A la F are lungimea 4, drumul minim de la A la H nu există (∞) şi aşa mai departe.

-Aha…cred că am priceput.

-Da? Hai să te văd! Vreau ca tu să faci programul în MinGW. Promit că mai dau o bere dacă reuşeşti.

-Aaa…păi ce nu face omu’ pentru o bere? Da’ lasă-mă să mă concentrez…

Deci…eu scriu pe hârtie şi tu îmi zici dacă greşesc.-Bine Gigele. Cum vrei tu.-Fii atent:

#include<iostream.h>

#include<fstream.h>

const int max=15000;

int c[20][20],d[20],t[20],p[20],n,m,s;

ifstream f("date.in");

ofstream g("date.out"); 

void citire()

{ int i,j,x,y,cost;

f>>n>>m;

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

if(i==j) c[i][j]=0;

else c[i][j]=max

else c[i][j]=max;

for(i=1;i<=m;i++)

{ f>>x>>y>>cost;

c[x][y]=cost;

}

}

Gigele, nu uita punctul

şi virgula!

void pr(int s){ int i,j,k,min; for(i=1;i<=n;i++) { d[i]=c[s][i]; if(i!=s && d[i]!=max) t[i]=s; } p[s]=1; for(k=1;k<n;k++) { min=max; for(i=1;i<=n;i++) if(!p[i] && d[i]<min) { min=d[i]; j=i;

} for(i=1;i<=n;i++) if(!p[i]) if(d[i]>d[j]+c[j][i])

{ d[i]=d[j]+c[j][i]; t[i]=j; }

p[j]=1; }}

void drum(int i)

{ if(t[i]) drum(t[i]);

g<<i<<" ";

}

 

void main()

{ citire();

f>>s;

pr(s);

for(int i=1;i<=n;i++)

if(i!=s

if(i!=s)

{g<<s<<"->"<<i<<": ";

drum(i);

g<<"="<<d[i]<<endl;

}

}

Gigeleee, paranteza

Gigele!

Gigel a terminat în sfârşit problema, însă afară soarele apare, parcă mahmur, pe cer.

-Pfoa!!! Şi reuşisem să-i dau de cap. -Lasă, Gigele, că mai e şi mâine o zi! Te

aştept tot aici, că nu ştiu dacă mai ajung acasă.

-Ai dreptate…măcar ştiu cum să procedez de acum înainte.

-Păi da! Vezi că e şi informatica asta bună la ceva?

-Să ştii că e. Hai să mergem acasă.-Hai! Da’ mai întâi…mai luăm o bere?

Project produced by…

Milotin Andrei-Cristian

and

Bălă Maria-Alexandra

Dar să nu îl uităm pe...

Mitruţă Cosntantin-Răzvan