| Fişierul intrare/ieşire: | camionas.in, camionas.out | Sursă | FMI No Stress 4 |
| Autor | Teodor Plop | Adăugată de |  FMI No Stress •fmins123 |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 12288 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.Vezi solutiile trimise | Statistici
Camionas
A fost odata un camionas care se afla intr-un basm. In lumea basmului existau N sate, numerotate de la 1 la N si M drumuri bidirectionale de legatura intre ele. Cum nici macar in basme drumurile nu sunt construite cum trebuie, fiecare din cele M drumuri au o rezistenta gi. Basmul nostru este insa un basm modern, iar PIZZA este unul dintre elementele de baza ale acestuia. Camionasul nostru are o greutate G si se afla initial, in satul 1. Acesta are misiunea de a transporta PIZZA din satul 1, catre satul N. Fiind foarte de treaba, camionasul se gandeste ca nu ar fi indicat sa mearga pe drumuri care au rezistenta mai mica strict decat greutatea sa, pentru ca aceste drumuri s-ar strica. Totusi, cum livrarea de PIZZA este menirea sa pe lume, acesta se intreaba care este numarul minim de drumuri a caror rezistenta trebuie marita, astfel incat el sa poata transporta PIZZA din satul 1 in satul N, fara sa fie nevoit sa mearga pe drumuri cu rezistenta strict mai mica decat greutatea sa.
Cum camionasul nostru nu este tocmai un expert in teoria grafurilor, s-a gandit ca tocmai voi il puteti ajuta, furnizandu-i raspunsul la aceasta intrebare.
Date de intrare
Fişierul de intrare camionas.in contine pe prima linie trei numere naturale, N M G, avand semnificatia din enunt. Pe urmatoarele M linii se vor gasi perechi de cate trei numere naturale, x y g, semnificand existenta unui drum intre satele x si y, de rezistenta g.
Date de ieşire
În fişierul de ieşire camionas.out se va gasi un singur numar natural, reprezentand numarul minim de drumuri a caror rezistenta trebuie marita, astfel incat camionasul sa isi poata duce la bun sfarsit misiunea.
Restricţii
- 1 ≤ N ≤ 50.000
- 1 ≤ M ≤ 100.000
- 1 ≤ G ≤ 1.000.000
- 1 ≤ gi ≤ 1.000.000
- Se garanteaza ca exista cel putin un lant intre satul 1 si satul N.
- PIZZA este elementul cheie in rezolvarea acestei probleme!
Exemplu
| camionas.in | camionas.out |
|---|---|
| 6 6 7 1 2 8 2 5 6 5 6 5 1 3 7 3 4 11 4 6 3 | 1 |
Explicatie
Camionasul, de greutate 7, are de ales intre doua rute: 1, 2, 5, 6 si 1, 3, 4, 6. In prima ruta, exista doua drumuri cu rezistenta mai mica decat 7, drumurile 2 - 5 si 5 - 6, pe cand in a doua ruta, exista un singur drum cu rezistenta mai mica decat 7, drumul 4 - 6.
