Pagini recente » Borderou de evaluare (job #2182679) | Borderou de evaluare (job #1286484) | Borderou de evaluare (job #2522557) | Cod sursa (job #1742303) | Diferente pentru grigore-moisil-2010/solutii/transport2 intre reviziile 4 si 5
Nu exista diferente intre titluri.
Diferente intre continut:
h2(#transport2). 'Transport2':problema/transport2
*Soluţie 1*
Pentru a afla costul de la nodul $1$ la nodul $N$, vom utiliza un algoritm asemănător cu 'algorimul lui Dijkstra':problema/dijkstra . Astfel vom determina pentru fiecare nod costul până în nodul $1$. Această soluţie are complexitatea $O(M logN)$.
Pentru a afla costul de la nodul $1$ la nodul $N$, vom utiliza 'algorimul lui Dijkstra':problema/dijkstra puţin modificat. Astfel, vom reţine pentru fiecare nod, valoarea minimă între nodul $1$ şi nodul respectiv. Când dorim să mergem în vecinii nodului curent trebuie verificat dacă $min(costul_nodului_curent, costul_muchiei) > costul_nodului_vecin$. Complexitatea acestui algoritm este $O(M logN)$.
*Soluţie 2*
Vom căuta binar răspunsul între 1 şi valoarea maximă pe care o poate avea o muchie. Pentru o valoare fixată, vom considera doar muchiile cu valoarea mai mare sau egală cu valoarea fixată şi vom utiliza o 'parcurgere în adâncime':problema/bfs pentru a vedea dacă nodurile $1$ şi $N$ sunt în aceeaşi componentă conexă.
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.