pscnv

PScNv

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

==Include(page="template/taskheader" task_id="pscnv")==

Poveste ...

Comisia preOni era in pana de probleme frumoase pe care sa le propuna la etapa finala celor mai talentati informaticieni din tara. Au fost deja alese probleme la toate grupele de varsta, dar mai era nevoie de o problema simpla la clasele XI-XII. O prioritate in alegerea problemelor pentru concurs si mai ales pentru finala a fost existenta unui numar mare de solutii astfel incat concurentii sa poata fi departajati usor. Astfel si-a facut aparitia problema simpla cu mai multe nivele:
Se da un graf orientat cu $n$ noduri si $m$ arce, fiecare arc are o pondere $k{~i~}$. Se dau doua noduri $x$ si $y$. Se cere determinarea valorii $k$ minime astfel ca sa existe un drum de la nodul $x$ la nodul $y$ cu proprietatea ca fiecare arc de pe drum are ponderea $k{~i~}$ mai mica sau egala decat $k$. Intre nodurile $x$ si $y$ va exista intotdeauna un drum.

h2. Cerinta

...

Aflati numarul $k$ minim!

h2. Restrictii

h2. Date de Intrare

...

Fisierul $pscnv.in$ va contine pe prima linie patru numere intregi ce reprezinta valoarile lui $n, m, x$ si $y$. Pe urmatoarele $m$ linii se vor afla cate trei numere intregi $x{~i~}, y{~i~}$ si $k{~i~}$ separate cate un singur spatiu ce reprezinta un arc $x{~i~}$ fiind nodul din care pleaca arcul, $y{~i~}$ nodul in care ajunge si $k{~i~}$ reprezentand ponderea arcului.

h2. Date de intrare

h2. Date de Iesire

...

Fisierul $pscnv.out$ va contine un singur numar intreg ce reprezinta valoarea minima a lui $k$.

h2. Date de iesire

h2. Restrictii

...

* $1 ≤ n ≤ 250.000$
* $1 ≤ m ≤ 500.000$
* $1 ≤ k{~i~} ≤ 1000$
* Pot exista mai multe arce intre doua noduri. De asemenea pot exista arce de la un nod la acelasi nod.
* *ATENTIE!* In cazul in care lucrati in C/C++ se recomanda citirea cu functii precum fgets din cauza dimensiunii mari a fisierelor de intrare!
 
h2. Nivele
 
* Pentru $30%$ din punctaj $n ≤ 1.000 m ≤ 10.000$
* Pentru $50%$ din punctaj $n ≤ 25.000 m ≤ 50.000$
* Pentru $80%$ din punctaj $n ≤ 100.000 m ≤ 200.000$

h2. Exemplu

| pscnv.in | pscnv.out |
| linia1
linia2
linia3
| linia1
linia2
|

table(example). |_. pscnv.in |_. pscnv.out |
| 4 5 1 4
1 2 3
1 3 1
2 4 2
3 2 2
3 4 3 | 2 |
 
h3. Explicatie

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

Drumul $1->3->2->4$ are ponderile muchiilor $1$, $2$ respectiv $2$.
 
==Include(page="template/taskfooter" task_id="pscnv")==
 
 

931