Fişierul intrare/ieşire:camionas.in, camionas.outSursăFMI No Stress 4
AutorTeodor PlopAdăugată defmins123FMI No Stress fmins123
Timp execuţie pe test0.2 secLimită de memorie12288 kbytes
Scorul tăuN/ADificultateN/A

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.incamionas.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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content