== include(page="template/taskheader" task_id="transport2") ==
Poveste şi cerinţă...
Se cunoaşte că un autovehicul nu poate circula pe un drum decât dacă masa sa nu depăşeşte masa maximă autorizată a drumului. În calcularea masei autovehiculului se consideră şi pasagerii, mărfurile etc.
h3. Cerinţă
Astfel, se dă o hartă sub forma unui graf neorientat, unde nodurile numerotate de la $1$ la $n$ reprezintă localităţile, iar muchiile reprezintă drumurile, împreună cu o masă maximă autorizată. Determinaţi greutatea maximă a unui autovehicul care poate ajunge legal din sursă (nodul $1$) la destinaţie (nodul $n$).
h2. Date de intrare
Fişierul de intrare $transport2.in$ ...
Fişierul de intrare $transport2.in$ conţine pe prima linie două numere naturale $n$ şi $m$, reprezentând numărul nodurilor şi, respectiv, numărul muchiilor. Pe următoarele $m$ linii se află câte trei numere naturale $x$ $y$ $w$, separate prin câte un spaţiu, reprezentând o muchie de masă maximă autorizată $w$ între nodurile $x$ şi $y$.
h2. Date de ieşire
În fişierul de ieşire $transport2.out$ ...
În fişierul de ieşire $transport2.out$ veţi afişa o singură valoare, reprezentând greutatea maximă admisă a unui autovehicul care poate ajunge legal din nodul $1$ în nodul $n$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $2 ≤ n ≤ 100 000$
* $1 ≤ m ≤ 200 000$
* $1 ≤ w ≤ 10 000$
* Ministrul transporturilor a decis că toate drumurile au masa maximă autorizată un număr întreg.
* Se garantează că există cel puţin un drum care leagă nodul $1$ de nodul $n$.
h2. Exemplu
table(example). |_. transport2.in |_. transport2.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 6 9
1 2 5
1 4 3
2 4 2
2 3 6
4 5 4
3 4 5
3 5 1
3 6 3
5 6 5
| 4
|
h3. Explicaţie
...
Soluţia corespunde traseului $1$ - $2$ - $3$ - $4$ - $5$ - $6$ ce are costurile $5$, $6$, $5$, $4$ şi respectiv $5$. Orice alt traseu va avea o greutate maximă autorizată mai mică decât $4$.
== include(page="template/taskfooter" task_id="transport2") ==
