Fişierul intrare/ieşire:sate.in, sate.outSursăpreONI 2007 Runda Finala
AutorFilip Cristian BuruianaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.2 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.insate.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content