Revizia anterioară Revizia următoare
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 . Astfel vom determina pentru fiecare nod costul până în nodul 1. Această soluţie are complexitatea 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 pentru a vedea dacă nodurile 1 şi N sunt în aceeaşi componentă conexă.
Soluţie 3
Pentru fiecare valoare vom reţine ce muchii au valoarea respectivă. Apoi, vom itera prin toate valorile posibile începând de la cea maximă şi la fiecare pas vom uni nodurile care sunt legate prin muchia respectivă folosind structura mulţimi disjuncte. Ne vom opri în momentul în care nodurile 1 şi N sunt în aceeaşi componentă conexă, rezultatul fiind prima valoare pentru care nodurile 1 şi N se află în aceeaşi componentă conexă.
