Nosaukums
Ātrs un bez ežastības (ff4)
Laika limits
0.50s
Atmiņas limits
64.0 MB
Grūtība
67%

Definīcija

Ezis Toretto™ un viņa bruņurupuču-jājošā ģimene vēlas aplaupīt skudrulāču kontrolēto pārvedumu ar kukaiņiem. Pārvedums notiek jau pēc 3 stundām un šāda iespēja vairs nebūs līdz nākamajam pilnmēnesim. Ir jārīkojas tagad!

Ir tikai viena problēma: viņš nezina ne pārveduma sākuma atrašanās vietu, ne tā maršutu. Toties ir zināms, ka skudrulāči atgriezīsies sākuma pozīcijā un vienu un to pašu ceļu neizmantos divas reizes.

Kā Eža Toretto™ ģimenei sadalīties pa pilsētu, lai vismaz viena grupa sastaptos ar skudrulāču pārvedumu?

Ežu izvietojums parauga testā


Ievaddatu raksturojums

Pirmajā rindā dots pilsētas krustojumu škaits n un ceļu skaits m. Katrs celš savieno 2 krustojumus. (3 ≤ ≤ m ≤ 105).

Tālāk seko m rindas, katra saturot 3 skaitļus a, b, c – krustojumi a un b, kurus savieno ceļš, un uz ceļa novietojamo ežu skaits c, kas vajadzīgs, lai garantēti aplaupītu pārvedumu (0 < a, b ≤ n, a ≠ b, 0 < c < 100).

Neviens ceļš ievaddatos neatkārtosies un visi ceļi ir divvirziena.


Izvaddatu raksturojums

Vienīgajā rindā jaizvada minimālais ežu skaits, kas vajadzīgs, lai garantētu pārveduma aplaupīšanu. 


Piezīmes

Parauga testā tiek novietoti 2 eži uz ceļa 1-2 un 3 eži uz ceļa 3-5.


Paraugdati

Stdin
6 7
1 2 2
2 4 6
1 6 3
2 5 5
4 3 4
6 5 4
5 3 3
Stdout
5

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.

Informējam, ka portālā tiek izmantotas sīkdatnes (angļu val. "cookies"). Turpinot lietot šo portālu, Jūs piekrītat, ka mēs uzkrāsim un izmantosim sīkdatnes Jūsu ierīcē.
Uzzināt vairāk