Din nefericire elfii trebui să ia măsuri drastice pentru a se apăra de pericolele externe.
Ei trebuie să amplaseze pe cărările care leagă satele lor câte un străjer la fiecare cel mult 1000 de pași. De exemplu, pentru o cărare care are lungimea de 24500 de pași vor fi necesari 25 de străjeri care să o păzească. Pentru ca numărul total al străjerilor să fie cât mai mic ei vor distruge anumite cărări astfel încât să rămână doar cele care sunt păzite. Evident, cărările care rămân sunt alese astfel încât să se poată călători între oricare două sate ale elfilor. Cele n sate ale elfilor sunt identificate prin numere cuprinse între 1 și n.
Fișierul de intrare INPUT.TXT conține pe prima linie numărul n al satelor elfilor.
Pe cea de-a doua linie a fișierului se află numărul total m al cărărilor dintre sate. Fiecare dintre următoarele m linii conține câte trei numere întregi, separate prin câte un spațiu. Primele două identifică două sate care sunt unite printr-o cărare, iar al treilea indică lungimea (exprimată în pași) a cărării.
Fișierul de ieșire OUTPUT.TXT trebuie să conțină pe prima linie numărul total al străjerilor necesari.
Fiecare dintre următoarele m linii va conține câte două numere întregi și un caracter. Cele două numere vor indica satele unite de o cărare, iar caracterul va indica dacă acea cărare va fi păzită sau distrusă. Pentru cărările păzite caracterul va fi P, iar pentru cele distruse caracterul va fi D.
INPUT.TXT
6 11 1 2 2500 1 4 900 1 5 3700 1 6 1100 2 3 3000 2 4 2900 3 4 1500 3 5 3800 4 5 2700 4 6 800 5 6 2200 OUTPUT.TXT 10 1 2 D 1 4 P 1 5 D 1 6 D 2 3 P 2 4 D 3 4 P 3 5 D 4 5 P 4 6 P 5 6 D
|