| Fişierul intrare/ieşire: | autobuz.in, autobuz.out | Sursă | ad-hoc |
| Autor | Florin Avram | Adăugată de |  avram florin constantin •avram_florin |
| Timp execuţie pe test | 0.5 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Autobuz
Aceasta este o problema medie.
Gigel are un autobuz si, fiindca este un bun cetatean vrea sa transporte persoane cu autobuzul sau. Cum drumurile nu au o infrastructura foarte buna,se impune o limita maxim admisa de pasageri.
Cerinta
Se da o harta, codificata sub forma unui graf neorientat unde nodurile numerotate de la 1 la n reprezintă localităţile, iar muchiile reprezintă drumurile, impreuna cu numarul maxim de pasageri admisi. Determinaţi numarul maxim de pasageri pe care Gigel ii poate transporta, legal, plecand din orasul 1 pana in orasul N.
Date de intrare
Fişierul de intrare autobuz.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 p, separate prin câte un spaţiu, cu urmatoare semnificatie, pe drumul de la orasul x la orasul y se pot transporta maxim p pasageri.
Date de ieşire
În fişierul de ieşire autobuz.out veţi afişa o singură valoare, reprezentând numarul maxim de pasageri pe care Gigel in poate transporta, legal, din orasul 1 în orasul N.
Restricţii
- 2 ≤ N ≤ 100 000
- 1 ≤ M ≤ 200 000
- 1 ≤ p ≤ 10 000
- Se garanteaza ca exista un drum din orasul 1 in orasul N
- Gigel nu este pasager.
Exemplu
| autobuz.in | autobuz.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
Gigel urmeaza urmatorul traseu: 1 -> 2 -> 3 -> 4 -> 5 -> 6 si poate transporta maxim 4 pasageri.
