Fişierul intrare/ieşire:transport2.in, transport2.outSursăGrigore Moisil 2010, Clasele 11-12
AutorMarius StroeAdăugată deMariusMarius Stroe Marius
Timp execuţie pe test0.5 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.intransport2.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content