Inverseaza reviziile

Diferente pentru problema/sate intre reviziile #22 si #1

Diferente intre titluri:

Sate

sate

Diferente intre continut:

== include(page="template/taskheader" task_id="sate") ==

Intr-o tara pitoreasca, intr-un judet de munte, sunt $N$ sate coliniare numerotate cu numere naturale de la $1$ la {$N$}. Satele sunt asezate in ordine, de la stanga la dreapta, conform numerelor care le identifica. Astfel, satul $1$ este cel mai din stanga, in timp ce satul $N$ este cel mai din dreapta. Sunt exact $M$ perechi de sate intre care distanta este cunoscuta ( exprimata in kilometri ). Pe baza acestor informatii, trebuie determinata distanta intre satele $X$ si $Y$, daca acest lucru este posibil.

Poveste si cerinta...

h2. Date de intrare

Pe prima linie a fisierului $sate.in$ se afla {$N$}, {$M$}, {$X$} si {$Y$}, unde $N$ este numarul de sate si $M$ este numarul de relatii de forma precizata mai sus. Pe fiecare din urmatoarele $M$ linii se gaseste cate un triplet ({$i j D$}), cu semnificatia ca distanta intre satele $i$ si $j$ ({$i < j$}) este de $D$ kilometri.

...

h2. Date de iesire

Fisierul de iesire $sate.out$ contine o valoare indicand distanta determinata intre satele $X$ si $Y$.

...

h2. Restrictii

* $1 &le; N &le; 30 000$
* $1 &le; M &le; 100 024$
* Pentru cel putin {$45%$} din teste, {$N &le; 300$}
* Relatiile date nu sunt contradictorii
* Se garanteaza ca distanta intre satele $X$ si $Y$ este determinata in mod unic de relatiile date
* Distanta dintre oricare doua sate este un numar natural exprimat in kilometri
* Se garanteaza ca distanta intre satele $1$ si $N$ nu depaseste $20$ de milioane
* Intotdeauna va putea fi determinata distanta dintre $X$ si $Y$ pe baza informatiilor primite

* $... &le; ... &le; ...$

h2. Exemplu
table(example). |_. sate.in |_. sate.out |

|11 7 1 11
1 7 10
4 6 4
5 7 4
6 8 5
2 10 15
4 11 13
5 8 8
|18
|

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

== include(page="template/taskfooter" task_id="sate") ==

h3. Explicatie
 
...
== include(page="template/taskfooter" task_id="sate") ==

Nu exista diferente intre securitate.

Diferente intre topic forum:

1954