| Fişierul intrare/ieşire: | sate.in, sate.out | Sursă | preONI 2007 Runda Finala |
| Autor | Filip Cristian Buruiana | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.1 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
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.
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.
Date de iesire
Fisierul de iesire sate.out contine o valoare indicand distanta determinata intre satele X si Y.
Restrictii
- 1 ≤ N ≤ 30 000
- 1 ≤ M ≤ 100 024
- Pentru cel putin 45% din teste, N ≤ 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
Exemplu
| 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 |
