Fișierul intrare/ieșire channels.in, channels.out Sursă Shumen 2012 juniori
Autor Georgi Georgiev Adăugată de avatar Marcela Marcela Marcela
Timp de execuție pe test 0.2 sec Limită de memorie 5120 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Channels (clasa a 8-a)

In Waterland, există n lacuri (numerotate de la 1 la n) și m canale care fac legătura între ele. Lățimea (în metri) a fiecărui canal este cunoscută. Pe canale se poate naviga în ambele direcții. Se știe că o barcă cu lățime de un metru poate naviga pe oricare canal.

Cerință

Scrie un program, care calculează numărul minim de canale care ar trebui să fie lărgite, astfel încât o barcă cu lățime de k metri să poată face o excursie între fiecare două lacuri (barca poate trece de la un lac la altul dacă lățimea sa este mai mică sau egală cu lățimea canalului care leagă lacurile).

Date de intrare

Fișierul de intrare channels.in conține pe prima linie numerele întregi n și m.
Pe fiecare din următoarele m linii sunt date trei numere întregi i, j si w, care arată că există un canal de lățime w între lacurile i și j (1≤i, j≤n).
Pe ultima linie este dat k, întreg.

Date de ieșire

Fișierul de ieșire channels.out va conține numărul minim de canale care ar trebui să fie lărgite.

Restricții

  • 1 < n ≤ 1000
  • 1 < m ≤ 100000
  • 1 ≤ w ≤ 200
  • 1 ≤ k ≤ 200

Exemplu

channels.in channels.out
6 9
1 6 1
1 2 2
1 4 3
2 3 3
2 5 2
3 4 4
3 6 2
4 5 5
5 6 4
4
2

Trebuie să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii