Diferente pentru problema/zapezi intre reviziile #2 si #8

Nu exista diferente intre titluri.

Diferente intre continut:

== include(page="template/taskheader" task_id="zapezi") ==
Poveste si cerinta...
Zapada a luat din nou prin surprindere primaria. Primarul a chemat de urgenta serviciul deszapeziri si a dat o lista cu strazile din oras care trebuie sa fie obligatoriu curatate. Primarul a selectat strazile din lista astfel incat numarul lor sa fie cat mai mic posibil, dar totusi intre oricare doua intersectii din oras sa existe legatura. La serviciul deszapeziri lucreaza doi angajati, Vasilica si Ionica, pe doua utilaje. In acest moment si angajatii si utilajele se gasesc la sediul serviciului deszapezri, situat in una dintre intersectiile din oras. Un utilaj de deszapezire consuma 1 litru de benzina/1 metru (indiferent daca se deplaseaza pe o strada inzapezita sau deszapezita).
Vasilica si Ionica trebuie sa deszapezeasca toate strazile din lista data de primar, astfel incat cantitatea totala de benzina consumata sa fie minima. Cand toate strazile din lista data de primar sunt curatate, utilajele pot fi parcate in ultima intersectie vizitata. Evident Ionica si Vasilica nu trebuie sa-si parcheze utilajele neaparat in aceeasi intersectie. Scrieti un program care sa determine cantitatea minima de benzina necesara pentru curatarea tuturor strazilor din lista data de primar.
h2. Date de intrare
...
Fisierul de intrare $zapezi.in$ contine:
 
* pe prima linie doua numere naturale $N$ si $S$, unde $N$ este numarul de intersectii din oras, iar $S$ este numarul de ordine al intersectiei in care se afla sediul serviciului deszapeziri, cea din care pleaca initial Vasilica si Ionica (intersectiile sunt numerotate de la $1$ la $N$).
* fiecare dintre urmatoarele $N-1$ linii contine 3 numere naturale $A B C$ cu semnificatia "intersectiile $A$ si $B$ sunt conectate direct printr-o strada de lungime $C$ metri".
h2. Date de iesire
...
Fisierul de iesire $zapezi.out$ contine pe prima linie cantitatea minima de benzina necesara pentru curatarea tuturor strazilor din lista data de primar.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 10.000$
* $1 ≤ S, A, B ≤ N$
* $1 ≤ C ≤ 1.000$
h2. Exemplu
table(example). |_. zapezi.in |_. zapezi.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|
 
h3. Explicatie
 
...
| 5 2
1 2 1
2 3 2
3 4 2
4 5 1
| 6 |
| 5 1
1 2 1
2 3 1
3 5 1
3 4 1 | 5 |
| 4 1
1 3 2
1 2 3
1 4 4 | 11 |
== include(page="template/taskfooter" task_id="zapezi") ==
 

Nu exista diferente intre securitate.

Diferente intre topic forum:

 
1858