| Fişierul intrare/ieşire: | transport2.in, transport2.out | Sursă | Grigore Moisil 2010, Clasele 11-12 |
| Autor | Marius Stroe | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Transport2
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.
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).
Date de intrare
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.
Date de ieşire
Î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.
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.
Exemplu
| transport2.in | transport2.out |
|---|---|
| 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 |
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.
